I got a theta notation question here as well that im kinda stuck on.
Select a theta notation for each of the following functions, and justify your answers thoroughly.
a) root(n) + n + 3nlogn
b) 2 + 4 + 8 + ... + 2^n
don't really know how to do it and my only initial guesses were a) theta(nlgn) and b) theta(2^n), theta(C^n) c > 1 or theta(C^(n+1)) C > 1
for n>e:
n log(n) > n > sqrt(n), so:
root(n) + n + 3n log(n) < 5n log(n),
and of course:
3n log(n) < root(n) + n + 3n log(n)
so:
3n log(n) < root(n) + n + 3n log(n) < 5n log(n)
so: root(n) + n + 3n log(n) = THETA(n log(n)
(note assumption that log denotes log_e here)
RonL