Algorithm Complexity

hello
i have an algorithm that i try to figure out it's complexity

for x = 1 to n/2
for y = x to n-x
for w = x to y
do (operation)

is it some kind of a familiar series?
how do i analyse it?
thanks
mike

Without more information about the 'operation' part, it is impossible to say. For example, if the 'operation' is to exit all three loops immediately, the complexity will be a lot different than if the operation is to multiply two matrices of size n^2.

Centering a screen?

Quote:

---

Originally Posted by MikeSan

for x = 1 to n/2
for y = x to n-x
for w = x to y
do (operation)

---

There is something wrong with your loop values. Let's take n = 100 for example:

x = 1 to 100/2 => x = 1 to 50
y = 50 to 100 - 50 => x = 50 to 50

Are you sure these are correct?

1) Outer loop runs for N/2 times
2) First Inner loop runs for N/2 Times
Starts from x, x+1, x+2... n-x. So, exactly for N/2 iterations, X >= N-X.
3) Innermost loop runs for N/2 Times again.
Starts from X=1 & Y=1, X=1 & Y=2.... X=1 & Y=N/2

So the complexity would be near to n/2 * n/2 * n2 ~ O(n*n*n)

-Kiran Kaki

Quote:

---

Originally Posted by MikeSan

hello
i have an algorithm that i try to figure out it's complexity

for x = 1 to n/2
for y = x to n-x
for w = x to y
do (operation)

is it some kind of a familiar series?
how do i analyse it?

---

The inner loop will perform 'operation' exactly (x^2 + x - y^2 + y) / 2 times (I'll leave it up to you to verify that).
So, to figure out the complexity, you need to analyse the sum:
SUM(x=1 to n/2, SUM(y=x to n-x, (x^2 + x - y^2 + y) / 2))).
Since it's a double sum, it might be helpful to work out an example and write it down in a table (x in the rows and y in the columns, e.g.).