Exam 1

What is the formula for the sum of the first n natural numbers?

n(n + 1) / 2

What is the formula for the sum of the first n squares?

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

What is the formula for a geometric series?

a(1 - r^n) / (1 - r)

What is the formula for an infinite geometric series when |r| < 1?

a / (1 - r)

What is a triangular sum?

A sum of the form 1 + 2 + 3 + … + n OR n + (n-1) + (n-2)… + 1

What is the time complexity of a triangular loop?

O(n²)

When the inner loop depends on i (like j = 1 to i), what type of pattern is this?

A triangular loop

What is the total work of a triangular nested loop?

n(n + 1)/2 → Θ(n²)

When a nested loop has j running to i², what is the resulting complexity?

Θ(n³)

What is the first step when analyzing a loop where the inner loop depends on i?

Convert it into a summation over i

What is Big-O notation used for?

Describing the upper bound of a function’s growth rate

What does Big-O ignore?

Constants and lower-order terms

What is Big-O of 5n + 3?

O(n)

What is Big-O of n² + n?

O(n²)

What is Big-O of n log n + n²?

O(n²)

What is the dominant term rule in Big-O?

The fastest-growing term determines the complexity

What is the time complexity of a loop that runs n times?

O(n)

What is the time complexity of two nested loops each running n times?

O(n²)

What is the time complexity of three nested loops each running n times?

O(n³)

What is the time complexity of a loop where i *= 2 each iteration?

O(log n)

What is the time complexity of a loop where i /= 2 each iteration?

O(log n)

What is the time complexity of a loop where i += constant each iteration?

O(n)

What is the key idea behind a geometric loop pattern?

The loop variable changes by multiplication or division

What equation do you solve for loops with i *= 2?

2^k = n

What equation do you solve for loops with i /= 2?

n / 2^k = 1

What is the time complexity of a loop where k = n and k = k/3 each iteration?

O(log n)

What is the time complexity of a loop where k = n and k = k - 5 each iteration?

O(n)

What is the time complexity of a nested loop where inner loop runs log i times?

Θ(n log n)

What does ∑ log i simplify to?

Θ(n log n)

What is the correct growth rate order from slowest to fastest?

log n < √n < n < n log n < n² < 2^n < n!

Which grows faster: log n or n?

n

Which grows faster: √n or log n?

√n

Which grows faster: n log n or n²?

n²

Which grows faster: polynomial or exponential functions?

Exponential functions

What is the structure of a proof by induction?

Base case → Hypothesis → Inductive step

What is the base case in induction?

Prove the statement is true for the starting value

What is the inductive hypothesis?

Assume the statement is true for n = k

What is the inductive step?

Prove the statement is true for n = k + 1

What is the goal of the inductive step?

Show that P(k) implies P(k + 1)

What is the most common mistake in induction proofs?

Not using the inductive hypothesis correctly

When expanding (k + 1)², what do you get?

k² + 2k + 1

When expanding (k + 1)³, what do you get?

k³ + 3k² + 3k + 1

What is the identity for 2^(k+1)?

2 · 2^k

What is the factorization of k² + k?

k(k + 1)

What is the factorization of k² + 3k + 2?

(k + 1)(k + 2)

What is the key step in proving ∑ i = n(n+1)/2 using induction?

k(k+1)/2 + (k+1) = (k+1)(k+2)/2

What is the sum of the first n odd numbers?

n²

What does it mean to prove O(n²)?

Show f(n) ≤ c·n² for n ≥ n₀

What does it mean to prove Ω(n²)?

Show f(n) ≥ c·n² for n ≥ n₀

What does it mean to prove Θ(n)?

Show both upper and lower bounds

What pattern does T(n) = T(n−1) + n follow?

Triangular sum → Θ(n²)

What pattern does T(n) = T(n/2) + 1 follow?

Logarithmic → Θ(log n)

What pattern does T(n) = T(n/2) + n follow?

Linear work with shrinking input → Θ(n)

What pattern does T(n) = 2T(n/2) + n follow?

Divide and conquer → Θ(n log n)

What pattern does T(n) = 2T(n/2) + n² follow?

Dominated by n² → Θ(n²)

What pattern does T(n) = 3T(n/3) + n follow?

Balanced recursion → Θ(n log n)

What is the Master Theorem used for?

Solving recurrences of the form T(n) = aT(n/b) + O(n^d)

What do you compare in the Master Theorem?

a and b^d

When does Case 1 of the Master Theorem apply?

When a = b^d

When does Case 2 of the Master Theorem apply?

When a < b^d

When does Case 3 of the Master Theorem apply?

When a > b^d