HU Design and Analysis of Algorithms Worksheet

Hw1, due Thursday, September 161. Suppose that f (n) = ⇥(g(n)). Assume that both functions increase without limit.
(a) Must it be true that log f (n) = ⇥(log g(n))? Prove or disprove.
(b) Must it be true that 2f (n) = ⇥(2g(n) )? Prove or disprove.
2. (a) Suppose you have a function of two variables, n and k; for instance h(n, k).
If you are told that h(n, k) = O(n + k), what should that mean mathematically?
(b) Let f (n) = O(n) and g(n) = O(n). Let c be a positive constant.
Prove or disprove that f (n) + c · g(k) = O(n + k).
3. Let f (n) =
Pn
y=1 (n
6
· y 23 ).
Find a simple g(n) such that f (n) = ⇥(g(n)), by proving that f (n) = O(g(n)), and that f (n) =
⌦(g(n)).
Don’t use induction / substitution, or calculus, or any fancy formulas.
Just exaggerate and simplify for big-O, then underestimate and simplify for ⌦.