Find theta notation of the following while loop

问题:

I have the homework question:

1. Find a theta notation for the number of times the statement x = x + 1 is executed. (10 points).

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

This is what I have done:

Ok first let’s make it easier. We will fist find the order of growth of:

while (i >= 1)
{
   x = x + 1
   i = i/2
}

that has order of growth O(log(n)) actually log base 2

the other inner for loop will execute n times therefore the algorithm should be of order:

O(log(n)*n)

---

The part where I get confused is that I am supposed to find theta notation NOT big-O. I know that theta notation is suppose to bound the function on the upper and lower limit. Will the correct answer be Theta(log(n)*n)?

I have found the answer in this link but I don't know how you get to that answer. Why they claim that the answer is Theta(n) ?

回答1:

You should now prove it is also Omega(nlogn).

I won't show exactly how, since it is homework - but it is with the same principles you show O(nlogn). You need to show [unformally explnation:] that the asymptotic behavior of the function, is growing at least as fast as nlogn. [for big O you show it is growing at most at the rate of nlogn].

Remember that if a function is both O(nlogn) and Omega(nlogn), it is Theta(nlogn) [and vise versa]

p.s. Your hunch is true, it is easy to show it is not Omega(n), and thus it is not Theta(n)

p.s. 2: I think the author of the other answer confused with a different program:

i = n
while (i >= 1)
{
   for j = 1 to i //NOTE: i instead of N here!
   {
      x = x + 1
   }
   i = i/2
}

The above program is indeed Theta(n), but it is different from the one you have provided.

回答2:

Rephrasing your code fragment in a more formal way, so that it could be represented easily using Sigma Notation:

for (i = n; i >= 1; i = i/2 ) {
    for j = 1; j <= n; j ++) {
        x = x + 1; // instruction of cost 'c'
    }
}

We obtain:

回答3:

As @amit mentions I already have the upper limit of the function and that is Big-O which it actually is O(n*lgn). if I plot a table of that function I will get something like:

n   n*lng
1   0
2   2
3   4.754887502
4   8
5   11.60964047
6   15.509775
7   19.65148445
8   24
9   28.52932501
10  33.21928095

because that is big-O then that means that the real function will be bounded by those values. In other words the real values should be less than the values at the table. for example taking a point for instace when n=9 we know that the answer should be less than or equal to 28.52932501 by looking at the table

So now we are missing to find Omega and that is the other bound. I think that the lower bound function should be Omega(n) and then we will get the table

n   Omega(n)
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
.......

so that will be the other bound. If we take again point for example where n = 9 again then that will give us 9. that means that our real function should give us a value greater or equal to 9. based on our big-O function we also know that it should be les than or equal to 28.52932501