1. ## 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

2. 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

3. 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

4. Thanks heaps for that! Really appreciated.

Henrik