Design & Analysis of Algorithms

Asymptotic Order of Growth

Big oh, Omega, and Theta

What does it mean for t(n) to be in O(g(n))?

t(n) is bounded above by some constant multiple of g(n) for all sufficiently large n.

What does the set O(g(n)) actually represent?

g(n) must grow at least as fast as t(n) — g(n) is an asymptotic upper bound on t(n).

In t(n) ≤ c·g(n) for all n ≥ n0, what do c and n0 represent?

c is a positive constant multiplier; n0 is the point after which the inequality holds for all larger n

To prove 100n + 5 ∈ O(n²), what's the key inequality chain?

100n + 5 ≤ 100n + n (for n ≥ 5) = 101n ≤ 101n²

Since 101n ≤ 101n² for n ≥ 1, chaining the two inequalities proves the bound.

What values of c and n0 does that proof give for 100n + 5 ∈ O(n²)?

c = 101, n0 = 5

Are the constants c and n0 in a Big-O proof unique?

No — the definition allows freedom in choosing c and n0; multiple valid pairs can work

Different valid inequality chains can lead to different but equally correct (c, n0) pairs.

What's an alternate pair of constants proving 100n + 5 ∈ O(n²), using 100n + 5 ≤ 100n + 5n (for n ≥ 1) = 105n?

c = 105, n0 = 1

In plain terms, what must be true of g(n) relative to t(n) for t(n) ∈ O(g(n))?

g(n) must grow at least as fast as t(n) — it's an asymptotic upper bound

Big-O captures an upper bound on growth rate, not an exact match.

What does it mean for t(n) to be in Ω(g(n))?

t(n) ≥ c·g(n) for all n ≥ n0, for some positive constant c and nonnegative integer n0

This is the formal definition of Big-Omega: t(n) is bounded below by a constant multiple of g(n) for all sufficiently large n.

What does the set Ω(g(n)) actually represent?

g(n) must be slower than (or equal to) t(n) in terms of order of growth — Big-Omega gives a lower bound.

How does the growth-rate relationship in Ω(g(n)) contrast with O(g(n))?

In O(g(n)), g(n) must be faster (or equal); in Ω(g(n)), g(n) must be slower (or equal)

Big-O gives an upper bound (g grows at least as fast as t); Big-Omega gives a lower bound (g grows no faster than t).

What's the key inequality used to prove n³ ∈ Ω(n²)?

n³ ≥ n² for all n ≥ 0

Since n³ grows at least as fast as n² for every n ≥ 0, the inequality holds with no lower bound needed on n.

What values of c and n0 prove n³ ∈ Ω(n²)?

c = 1, n0 = 0

Since the inequality n³ ≥ n² holds for every n ≥ 0, we can pick the smallest possible constants: c = 1 and n0 = 0.

What does it mean for t(n) to be in Θ(g(n))?

c2·g(n) ≤ t(n) ≤ c1·g(n) for all n ≥ n0, for some positive constants c1, c2 and nonnegative integer n0

This is the formal definition of Big-Theta: t(n) is sandwiched between two constant multiples of g(n) for all sufficiently large n.

In c2·g(n) ≤ t(n) ≤ c1·g(n) for all n ≥ n0, how do c1, c2, and n0 work together?

c2 sets the lower bound and c1 sets the upper bound, both holding from the same n0 onward

Both bounds must hold using the same n0 — t(n) is bounded both above and below by positive constant multiples of g(n).

What does the set Θ(g(n)) actually represent?

All functions that have the same order of growth as g(n), up to a constant multiple, as n → ∞

Θ(g(n)) is the "tight bound" set — it combines both O(g(n)) and Ω(g(n)).

Every quadratic function an² + bn + c with a > 0 belongs to which Theta class?

theta (n²)

The an² term dominates for large n, and with a>0 the function is both upper- and lower-bounded by constant multiples of n² — a tight bound.

What is being shown?

L’Hopital’s rule

What formula is being shown?

Stirling’s formula

What algorithm is being shown?

Maximum element

What formula is being shown?

Maximum element

What algorithm is being shown?

Element Uniqueness

What formula is being shown?

Element uniqueness

3A_Brute Force_Bubble_selection - 7

What is the time complexity?

O(n²)

3A_Brute Force_Bubble_selection - 12

What is the time complexity?

O(n)

3A_Brute Force_Bubble_selection - 18

What is the time complexity?

O(n)

3A_Brute Force_Bubble_selection - 28

What is the time complexity?

O(n²)

2D_Recursive Analysis_ - 8

Solve the problem.

o(n²)

2D_Recursive Analysis_ - 11

Solve the problem.

O(n!)

2D_Recursive Analysis_ - 12

Solve the problem.

2D_Recursive Analysis_ - 27

What is the time complexity?

O(n)

3B_Exhaustive Search - 13

Give the tour and costs based on what is provided.

Tour Ex: a → c → d → b

Costs Ex: 2 + 4 + 8 + 7 =

3B_Exhaustive Search - 12

What is the time complexity for the traveling salesman problem?

O(n!)

3B_Exhaustive Search - 16

What is the time complexity of the Knapsack problem?

Omega(2^n)

3B_Exhaustive Search - 20

What is the time complexity of the Assignment problem?

O(n!)

3C_Graph Traversal - 11

Go through Depth-First Search (DFS) and get the DFS result and output tree.

1, 2, 3, 5, 4, 6

3C_Graph Traversal - 24

What is the time complexity of DFS? For adjacency matrix representation and adjacency list representation?

O( |V|² ), O ( |V| + |E| )

3C_Graph Traversal - 30

Give the DFS result and output tree.

DFS result: a, c, d, f, b, e

3C_Graph Traversal - 32

Give the DFS result and output tree.

0, 1, 2, 3, 4

3C_Graph Traversal - 38

Give the BFS result and output tree.

1, 2, 3, 6, 5, 4

3C_Graph Traversal - 53

Give the BFS result and output tree.

3C_Graph Traversal - 56

Give the BFS result and output tree.

1, 2, 3, 4

3C_Graph Traversal - 58

What is the time complexity of BFS? For adjacency matrix and adjacency list?

O( |V|² ), O( |V| + |E|)

3C_Graph Traversal - 63

DFS and BFS are used for what?

Stack, Queue

2C_Recursive Algorithms_ - 3

What is the time complexity?

O(n)

4A_DecreaseConquer_insort_topsort - 14

What algorithm is shown?

Insertion sort

4A_DecreaseConquer_insort_topsort - 15

What algorithm is shown?

Insertion sort

4A_DecreaseConquer_insort_topsort - 16

What algorithm is shown?

Insertion sort

4A_DecreaseConquer_insort_topsort - 19

Is this a directed acyclic graph (dag)?

Yes

4A_DecreaseConquer_insort_topsort - 19

Is this a directed acyclic graph (dag)?

No

4A_DecreaseConquer_insort_topsort - 22

Solve using topological sort.

C2 C1→ C3 → C4 → C5

4A_DecreaseConquer_insort_topsort - 24

Give the Solution

C1, C2, C3, C4, C5

4A_DecreaseConquer_insort_topsort - 30

Give the Solution

B → C → D → E → A

4A_DecreaseConquer_insort_topsort - 32

Give the Solution

2, 1, 0, 4, 3

Kahoot

____ are also called digraphs

directed graphs

Kahoot

A tree is a connected ____ graph.

Acyclic

Kahoot

Binary search tree nodes can have a maximum of two children.

T or F

True

Kahoot

What is the basic operation for sorting algorithms?

Comparison

Kahoot

Euclid’s algorithm includes ___

Mod

Kahoot

Sieve of Eratosthenes algorithm is to find prime numbers.

T or F

True

Kahoot

The function 2^n grows slower than function of (n^2)

T or F

False

Kahoot

The following assertion is incorrect - n^4 + n + 1 E=! O(n²).

False

Kahoot

L’hospital’s rule is associated with the

limit

Kahoot

Theta (n³) is the time complexity of ____ algorithm.

Matrix multiplication

Kahoot

Recursive algorithms must have

best case and recursive case

Kahoot

Each recursive algorithm can be realized with iterative approach.

T or F

True

Kahoot

To analyze recursive algorithms, We can use the ____ technique.

Backward substitution

Quiz Review

What is the time complexity for sequential search best case? And the base operation?

Theta(1), comparison

Quiz Review

What is the time complexity for sequential search worst case? And the base operation?

O(n), comparison

Quiz Review

What is the equation used for Euclid’s?

gcd(m,n) = gcd(n, m mod n)

Quiz Review

What are two main efficiency measures?

Time and space complexity

Quiz Review

Give the equation for the Tower of Hanoi.

2^n - 1

Quiz Review

What is the time complexity?

T(n) = 2T(n-1)+1

Theta(2^n)

Quiz Review

What is the time complexity?

T(n) - nT(n-1)

Theta(n!)

Quiz Review

What is the time complexity?

n

E 1

i = 1

n

Quiz Review

What is the time complexity?

i ← i * 2 loop

Theta(logn)

Quiz Review

What is the equation and time complexity for Maximum Element Comparison?

n - 1, Theta(n)

Quiz Review

What is the equation for this?

n

E i²

i = 1

(n(n+1)(2n+1))/ (6)

Quiz Review

What is the equation for this?

n

E i

i = 1

(n(n+1)) / 2

Quiz Review

What is adjacency list?

List of adjacent vertices for each vertex

Quiz Review

What is the time complexity of three full nested n loops?

Theta(n³)

Quiz Review

What is the time complexity of two full nested n loops?

theta(n²)

Quiz Review

Is queue FIFO or LIFO?

FIFO

Quiz Review

Is stack FIFO or LIFO?

LIFO

Quiz Review

What is being described?
A well-defined computational procedure input → output in a finite time.

Algorithm

Quiz Review

Give the time complexity order.

Constant time → Logarithmic → Linear → Log Linear → Quadratic → Cubic → Exponential → Factorial

Quiz Review

Give another version of this.

Constant time → Logarithmic → Linear → Log Linear → Quadratic → Cubic → Exponential → Factorial

1 < log < n < nlogn < n² < n³ < 2^n < n!

Quiz Review

What is the time complexity of an iterative Fibonacci?

Theta(n)

Quiz Review

What is the time complexity?

T(n) = T(n/3) + 1

theta(logn)

Quiz Review

What is the time complexity?

T(n) = T(n-1) +n

theta(n²)

Quiz Review

What is the time complexity?

m(n) - m(n-1) + 1

Theta(n)

Quiz Review

What is being described?

Store previously computed results to audio repeated computation.

Memorization

Quiz Review

What is being shown?

n(n-1) / 2

Element Uniqueness worst case

Quiz Review

What is the time complexity for element uniqueness worst case?

Theta(n²)