Theta Notation for algorithms question!

[Serg_zone]

Hey guys, i'm have a tough time working the following two problems. I need to find out the theta notation or big O for the number of times x=x+1 is executed

i = 1
while (i < n) {
  i = i^2;
  x = x + 1;
}

I tried to work this thing out and got Theta(2^n!). I doubt that this is right though

Here is the 2nd problem

for i = 1 to n
for j = 1 to i
for k = 1 to j
x = x + 1

I'm thinking that this one is Theta(n^3), but again i'm not so sure. Any help is greatly appreciated.

[Rashakil Fol]

The best way to verify the correctness of your answers is to try a few example values for your parameters and see what happens. See if you can notice a pattern. For example, if I were given the code for (i = 0; i < 2 * n; ++i) { x = x + 1; } and wanted to know how many times (x = x + 1) was evaluated in terms of theta notation of n, I might try a few example values for n and see what happens. For example, if n were 1, it'd get executed twice, and if n were 2, it'd get executed 4 times, and in general 2*n times, so the number of times it gets executed is Theta(n) times. (Saying Theta(2*n) or Theta(n + 1) or Theta(n/100) would also be equivalent to Theta(n), since they're all within a constant multiple of each other for large enough values of n.)

For the first problem, pick some values for n (and start x at zero, say). Then see the pattern. Yes, your answer is extremely wrong :-) And it's best to work out the code by hand than put it in a computer.

If you need to prove your answers, considerably more effort is required.

[Serg_zone]

That's exactly what i did. I guess i just don't understand the concept and the book doesn't explain much either.
Well, looking at the first one:

i = 1
while (i < n) {
  i = i^2;
  x = x + 1;
}

the loop becomes infinite if n > 1 since i always stays 1. In this case i have no idea what the theta notation is. O(n)? :rolleyes:

For the 2nd one

for i = 1 to n
for j = 1 to i
for k = 1 to j
x = x + 1

the sequence is 1,4,10,20,35,56...
I don't even see a pattern here. I'm actually more stuck now then i was before lol.

[ringy_thingy]

You are on the right track for the second one. One trick for the second problem is:
The second and third loops are dependent on the first loop, that varies from 1 to n. At some point (in the end) when the first loop takes the value 'n', the subsequent loops will go to n too, leading to O(n^3). A tighter analysis, can however give a better estimate, but as big O is kind of lousy on accuracy, you don't worry about it.

[AnonCSAddict]

Well think about what you just said about the first one, if n is greater than 1, then it goes on forever. Since Big-Oh is the worst case analysis and the worse case is never finishing, you can say that big-Oh is undefined for this loop. Go to wikipedia and you can see the formal definition for the notation. Notice that it is undefined as if the limit of the function goes to infinity since one of the conditions of big-Oh is that it is less than infinity.