Remember that square-root(n) = n^(1/2)
== 1 ==
True or false?
3 n^2 + 10 n log n = O(n lg n)
3 n^2 + 10 n log n = Omega(n^2)
3 n^2 + 10 n log n = Theta(n^2)
n log n + n/2 = O(n) FALSE
== 2 ==
Sort the following functions in increasing order of asymptotic running-time.
f1 = 2^(2^5000) =
f2 = 2^(4n)
f3 = n * square-root(n)
f4 = n2 * (lg (lg (lg n)))
== 3 ==
Prove that 5n + 6 = O(n^2) using the definition of O, providing a valid c and n0.
Can you find another valid c and n0 that proves that, as well?
== 4 ==
Given the recurrence equation:
T(n) = 2T(n/4) + square-root(n)
with T(1) = theta(1)
and consider its recurrence tree. (do not show it here, please answer the following questions).
What is the mathematical formula that describes the cost of each node?
What is the mathematical formula that describes sum of the sibling nodes at each level of the recurrence tree that is not the level of the leaves?
How manu leaves does the tree has? and what is the sum of their cost?
What is the running-time in theta notation?