Algorithm Complexity

[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?
thanks
mike

[Peter_B]

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.

[dglienna]

Centering a screen?

[ProgramThis]

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?

[Kiran143]

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

[D_Drmmr]

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.).