# Find theta notation

• May 12th 2007, 02:58 AM
cpklas
Find theta notation
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
• May 12th 2007, 06:55 AM
CaptainBlack
Quote:

Originally Posted by cpklas
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.

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

If n is a power of 3 we have the outer loop is executed ceil(log_3(n))
times with j=1, 3, 9, .., 3^k .. 3^{log_3(n}.

Then the inner loop is executed:

2, 6, .. , 2*3^{log_3(n)}

times.

So the number of times in assignment statement inside the inner most
loop is executed is:

N(n) = 2*[sum_{i=1 to log_3(n)} 3^i]

the sum is a finite geometric series, so:

N(n) = 2*(3^{log_3(n)+1}-1)/(3-1) = 3^{log_3(n)+1}-1 = 3*n - 1.

Now if n > 1, is not a power of 3 we have:

N(3^{floor(log_3(n)}) < N(n) < N(3^{floor(log_3(n)+1)})

Now:

N(3^{floor(log_3(n))}) = 3*3^{floor(log_3(n))}-1

............................. >= 3*(n-1) - 1 = 3*n -4

And:

N(3^{floor(log_3(n)+1)}) = 3*3^{floor(log_3(n)+1)} -1 <= 3*(n+2) - 1 = 3*n +5.

Hence:

3*n -4 <= N(n) <= 3*n +5.

So for n large enough (n > 4 should suffice):

2*n <= 3*n -4 <= N(n) <= 3*n +5 <= 6*n

2*n <= N(n) <= 6*n

Hence N(n)=THETA(n).

RonL
• May 12th 2007, 07:02 AM
CaptainBlack
Quote:

Originally Posted by cpklas
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

As t(12) = 34, clearly t(n) is not bounded above by 2n, at least when
n is as small as 12.

RonL
• May 14th 2007, 05:56 AM
cpklas
Thanks heaps for that! Really appreciated.

Henrik