Big-O

Question 1

Given functions:

• f(n) = 100n + log n
• g(n) = n + (log n)²

Which relationship holds? (Select one)

• [ ] f(n) = O(g(n))
• [ ] g(n) = O(f(n))
• [ ] f(n) = O(g(n)) and g(n) = O(f(n))

Answer 1

f(n) = O(g(n)) and g(n) = O(f(n))

• 100n and n are dominant terms (we can ignore logs)
• only differs by the constant so Big O-wise they are equal

Question 2

Given functions:

• f(n) = n log n
• g(n) = 10n log₁₀ n

Which relationship holds? (Select one)

• [ ] f(n) = O(g(n))
• [ ] g(n) = O(f(n))
• [O] f(n) = O(g(n)) and g(n) = O(f(n))

Answer 2

Answer: O(g(n)) and g(n) = O(f(n))

• Only differs by constant term
• Base of the log doesn’t change its Big-O (log_2 vs log_10)

Question 3

Given functions:

• f(n) = √n
• g(n) = (log n)³

Which relationship holds? (Select one)

• [ ] f(n) = O(g(n))
• [O] g(n) = O(f(n))
• [ ] f(n) = O(g(n)) and g(n) = O(f(n))

Answer 3

Answer: g(n) = O(f(n))

• n​ converts to n0.5
• (log n)^3 converts to 3 log n using the power rule.
• n^a dominates log n ^ a

Question 4

Given functions:

• f(n) = n​
• g(n) = 5log2​n

Which relationship holds? (Select one)

• [O] f(n) = O(g(n))
• [ ] g(n) = O(f(n))
• [ ] f(n) = O(g(n)) and g(n) = O(f(n))

Answer 4

Answer: f(n) = O(g(n))

• 5log2​n can be flipped to nlog2​5 using the exponent to log rule
• n​ converts to n0.5
• n0.5<n2.32, so g(n) dominates

Question 5

[DPV 0.2] Show that g(n) = 1 + a + a² + … + aⁿ is:

• O(aⁿ) when a > 1
• O(1) when a < 1

Answer 5

Geometric series:
S = a^{n+1} -1 / (a-1)

Given proof, we transform the problem into analyzing a closed-form expression:

• If a > 1, g(n) = O(a^n)
  
  • Denominator is a constant, numerator is dominated by an+1
  • We can ignore the denominator (since its a constant) the dominant term is a^n (can ignore +1)
  • Therefore, dominant term an gives us O(an)
• If a < 1, g(n) = O(1)
  
  • Denominator is negative constant, numerator is dominated by -1 (since a^n+1 approaches zero)
  • Therefore, the expression reaches a constant value, giving us O(1)
• If a = 1, g(n) = O(n)