algorithm problem: Find theta notation for numb. of times...

[rygard]

Find a theta notation for the number of times x = x +1 is executed.

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

I know the answer to this is theta(n^3) but i don't understand why. I'm having trouble understanding the examples I've seen of this or similar problems, I understand that the theta of something means a function that grows similarly, but after that I get confused. If anyone could help walk me through this problem, I'd appreciate it.

 

[stapel]

Find a theta notation for the number of times x = x +1 is executed.

Please forgive my ignorance, but: What is "theta notation"? In what mathematical discipline does it usually arise?

Thank you!

Eliz.

 

[ilaggoodly]

this is not actually "theta" notation you speak of, it is called "Big O" notation, since you are referring to the complexity of a computer science algorithm, i presume. you know the answer is O(n^3), well thats good. its pretty simple. to get big O notation, you take some function and remove all the constants, as they become unimportant, as x--> infinity. For this particular case, you have 3 nested for-loops, since the outer loop runs n times, and the inner loop runs n times per 1 run of the outer loop, obviously you have n^2 calculations, and then for the last nested loop, yo have it running i times, however as n approaches infinity it becomes similiar to i, and therefore you have O(n^3)

 

[rygard]

this is not actually "theta" notation you speak of, it is called "Big O" notation, since you are referring to the complexity of a computer science algorithm, i presume. you know the answer is O(n^3), well thats good. its pretty simple. to get big O notation, you take some function and remove all the constants, as they become unimportant, as x--> infinity. For this particular case, you have 3 nested for-loops, since the outer loop runs n times, and the inner loop runs n times per 1 run of the outer loop, obviously you have n^2 calculations, and then for the last nested loop, yo have it running i times, however as n approaches infinity it becomes similiar to i, and therefore you have O(n^3)

Yes, this is for complexity algorithms. I think I understand what you're saying, but the actual question was to find the theta notation for it, and the exact answer given for this particular problem in 2 different examples was theta(n^3). So does that mean in this particular case, that the worst case time and average case time are the same?

 

[rygard]

Oh wait nevermind about the part of O(n^3), I just remembered that you'd have to prove O(n^3) and omega(n^3) to have theta(n^3), so that makes sense. I don't exactly understand what you mean when you say n becomes similar to i as n approaches infinity.

 

[daon]

I made a post about theta/omega/big-o a while back. http://www.freemathhelp.com/forum/viewt ... =algorithm

For your problem, your algorithm has the following "look:"

\(\displaystyle \L \sum _{j=1}^n \sum _{i=1}^n \sum _{k=1}^i 1\)

Note that I have switched the order of i,j which is fine. This simplifies as:

\(\displaystyle \L \sum _{j=1}^n \sum _{i=1}^n i \,\, \,\, =\)

\(\displaystyle \L \sum _{j=1}^n \frac{n(n+1)}{2} \,\, = \,\, \frac{n^2(n+1)}{2} \,\, = \,\, \frac{1}{2}\(n^3 + n^2)\)
Clearly it is both \(\displaystyle O\(n^3\)\) and \(\displaystyle \Omega\(n^3\)\), since its easy to find non-negative constants \(\displaystyle a\) and \(\displaystyle b\) such that \(\displaystyle \frac{1}{2}\(n^3 + n^2) \,\, \le \,\, an^3\) and \(\displaystyle \frac{1}{2}\(n^3 + n^2) \,\, \ge \,\, bn^3\) for sufficiently large n. Think large integer for a and small rational < 1 for b.

In essence what this means is that you can expect it to be both "faster" and "slower" than an algorithm of complexity \(\displaystyle n^3\). Thus it is \(\displaystyle \Theta(n^3)\).

 

[rygard]

I think I'm starting to get the hang of this. I did another problem, that was very similar, I was wondering if you guys could check my work and answer.

Find a theta notation for number of times x = x + 1 is exectued

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

So I made a table, sort of like an x, y coordinate table, where n is the input and the output is the number of times x = x + 1 is executed for that input. My inputs in the "n" column are 1, 2, 3, 4, 5, and the outputs are 1, 8, 27, 64, and 125 respectively.

So I have the sequence

1 + 8 + 27 + 64 + 125 + . . . + n(n^2)

n * (n^2) = n^3, so the theta notation is theta(n^3)

How does that look?

 

[daon]

That is correct. Be careful to show that it is \(\displaystyle \Theta \( f\(n\) \)\) and not just say it. In this case it is obvious since \(\displaystyle f\(n\) \,\, \in \,\, \Theta \( f\(n\) \)\) is always true (f(n)=n^3). However, in the previous example you might be asked to find the constants and "cutoffs" (the smallest n the inequality holds for the constants you found) that make \(\displaystyle f\(n\) \,\, \in \,\, O \( n^3 \)\) and \(\displaystyle f\(n\) \,\, \in \,\, \Omega \(n^3\)\)...

Your class may be different, but all this rigor was important/required for my professor.

 

[rygard]

That is correct. Be careful to show that it is \(\displaystyle \Theta \( f\(n\) \)\) and not just say it. In this case it is obvious since \(\displaystyle f\(n\) \,\, \in \,\, \Theta \( f\(n\) \)\) is always true (f(n)=n^3). However, in the previous example you might be asked to find the constants and "cutoffs" (the smallest n the inequality holds for the constants you found) that make \(\displaystyle f\(n\) \,\, \in \,\, O \( n^3 \)\) and \(\displaystyle f\(n\) \,\, \in \,\, \Omega \(n^3\)\)...

Your class may be different, but all this rigor was important/required for my professor.

Yeah, I forgot to mention that my professor only told us to focus on the theta notation, not so much on proving it by showing omega and big O. This is an introduction to discrete math, algorithms, etc. and there is a course later on that focuses on designing/analyzing algorithms that deals with all the hard math and proofs, he only wanted to focus on the more general idea of it, just as an introduction. Thanks everyone for all your help!