Thread: Theta notation for functions

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

Originally Posted by Papakanos

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

On b) if you use the geometric sum formula to get (2^(n+1))/(2-1) - 1 = 2^(n+1) - 2

then

2^(n+1) - 2 > 2^n
2^(n+1) - 2 = lower(2^n)

2^(n+1) - 2 < 2*2^n
so 2^(n+1) - 2 = O(2^n)

so it should be theta(2^n)

Originally Posted by cpklas

On b) if you use the geometric sum formula to get (2^(n+1))/(2-1) - 1 = 2^(n+1) - 2

then

2^(n+1) - 2 > 2^n
2^(n+1) - 2 = lower(2^n)

2^(n+1) - 2 < 2*2^n
so 2^(n+1) - 2 = O(2^n)

so it should be theta(2^n)

with that shouldn't the - 2 on the right be a - 1 hence making the others all - 1 or am i missing something?
Although i get wat ur saying though.

and any tips on a) ?

cheers for the help so far

ahh ok. a + ar^1 + ar^2 +.... ar^n + ar^n+1 = a(r^(n+1) - 1) / (r - 1) - 1.

we get (r^(n+1) - 1) / (2 - 1) - 1 = (r^(n+1) - 1) - 1 = r^(n+1) - 2

Hence the -2

Henrik

Originally Posted by Papakanos

a) root(n) + n + 3nlogn

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