Hello, I have another problem I need some help with.

*I need to find out the theta notation for the number of times the statement x = x + 1 is executed, assuming that n is a positive integer in both cases. Justify your answers.*

Code:

j = n
while (j >= 1) {
for i = 1 to 2j
x = x + 1
j = floor(j/3)
}

I have tried with several n to see a pattern.

Code:

n=1 t(n)=2
n=2 t(n)=4
n=3 t(n)=8
n=4 t(n)=10
n=5 t(n)=12
n=6 t(n)=16
n=7 t(n)=18
n=8 t(n)=10
n=9 t(n)=26
n=10 t(n)=28
n=11 t(n)=30
n=12 t(n)=34

I found that f(n) = 2n + 2*floor(n/3) + 2*floor(n/9) + 2*floor(n/27) + .... and so on works. But how do I find out the theta notation from that?

Is it this simple: n <= f(n) <= 2n

so f(n) = theta(n) ?

I think I need to prove it somehow tho...

Any suggestions?

Cheers,

Henrik