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