ANALYSIS BIG-O NOTATION

For each of the following pairs of functions f(n) and g(n), state whether f(n) =
O(g(n)), f(n) = ­Ω(g(n)), or f(n) = Θ(g(n)), or none of the above:


(a) f(n) = n2 + 3n + 4, g(n) = 6n + 7
Sol: f(n) = ­Ω(g(n).


(b) f(n) = n √n , g(n) = n2 - n
Sol: f(n) = O(g(n)).


(c) f(n) = 2**n - n**2, g(n) = n**4 + n**2
Sol: f(n) = ­­Ω(g(n).


(d) Assume you have five algorithms with the running times
listed below (these are the exact running times). How much slower do each of these
algorithms get when you double the input size
i) n²
Sol: 4T(n)

ii) n³
Sol: 8T(n)

iii) 100n²
Sol: 4T(n)

iv) nlgn
Sol: 2n(lg2n) = 2n(1+lgn) ~ 2n lgn
T(n) = 2T(n)

v) 2ⁿ
Sol:  [T(n)]² 


(e)  Write a big-O expression for 1+2+3+...+n?
Sol:  O(n²)


True or false:
(f) An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
Sol : False


(g)  n! = O(nⁿ)
Sol: True


(h) n^O(1) = O(n²)
Sol: False.  O(1) can be any large constant .


(i) All of the following are true.

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), if c is constant
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))