San Diego State University Algorithm Worksheet

Problem 1Asymptotic Notation
For each of the following pairs of functions f (n) and g(n), say whether f (n) = O(g(n)), g(n) = O(f (n)),
f (n) = Θ(g(n)) (and therefore vice versa), or none of the above.
• f (n) = 5n4 + n3
g(n) = 5n4


n
• f (n) = n 1 + (−1)
g(n) = n
2
• f (n) = 100n − log n2
g(n) = 200 + log n2
• f (n) = 2n − (−2)n
g(n) = 2n − (−2)n+1 /5
• f (n) = 2n
g(n) = 2n+log 2n
Problem 2
Let f (n) and g(n) asymptotically positive functions. Prove that g(n) + f (n) = Θ(max(f (n), g(n))).
Problem 3
Prove or disprove that if f (n) = Θ(g(n)), then 4f (n) = Θ(4g(n) ).
Problem 4
Let f (n) and g(n) asymptotically positive functions and assume that limn→∞ g(n) = ∞. Prove that
if f (n) = Θ(g(n)), then Ln(f (n)) = Θ(Ln(g(n))).
Problem 5
Asymptotic Growth Rates
For each of the following functions, give its asymptotic growth rate in as simple a form as possible, using
the Θ notation.
• 24 log8 n
• 2n log n + 5n1.2
• 3n−log3 log3 n
• 10n4−(1/n)