Algorithm Analysis help

[sydney25]

I am trying to solve the following problem. Could someone let me know if my logic is right? The answer should be expressed in Theta notation.

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

The second loop is run c*(1+2+3+4+...+n) = n(n+1)/2, so it the running time is Theta(n^2)

If the third loop runs at (n-j+1). How do I combine this with the second loop to find a total running time? Is it still Theta(n^2)?

 

[Denis]

I am trying to solve the following problem. Could someone let me know if my logic is right? The answer should be expressed in Theta notation.
x = 0
for i = 1 to n do
for j = 1 to i do
for k = j to n do
x = x + 1
The second loop is run c*(1+2+3+4+...+n) = n(n+1)/2, so it the running time is Theta(n^2)
If the third loop runs at (n-j+1). How do I combine this with the second loop to find a total running time? Is it still Theta(n^2)?

Not sure what you're doing/asking...why is there no initial value for n?

Adding an "n loop" to your coding:

for n = 1 to 20
x = 0
for i = 1 to n do
for j = 1 to i do
for k = j to n do
x = x + 1
next i,j,k
print n,x
next n

These are the results (n,x):
1,1
2,5
3,14
4,30
...
10,385
...
20,2870
And x is the "sum of squares", of course.

 

[sydney25]

Thanks for the reply.

This is theory - n can be any number. If the 2nd loop runs at Theta(n^2).

1+2+3+4+...+n = n(n+1)/2 = Theta(n^2)

I am trying to figure out what the 3rd loop - the innermost loop, does to the run time. If you run the algorithm the loop "for k = j to n do" would give you

n + (n+(n-1)) + (n+(n-1)+(n-2)) + (n+(n-1)+(n-2)+(n-3))...

I believe this is Theta(n^3), but I need a way to mathimatically show this is true.