Thread: Big-O analysis

What is the Big-O analysis of this code? I think the code is doing a sort but I'm confused. Is this code comparing numbers for a sort and placing them in temporary cells?


r = 0
for i = 1 to N-1 do
for j = i+1 to N do
for k = 1 to j do
r = r+1;

Sorry, but thats all the code I have. We are studing sorting algorithms and the Big-O notations. A question given us is to give a Big-O analysis of the following code. Maybe thats why I'm scratching my head because there isn't enough code provided?

I'll try to explain:

[tag]

Big-O (order of magnitude) function gives a rounded-off measurement of the run time for an algorithm (usually the worst-case run-time). The function f(n) in O(f(n)) is the upper bound on the value of the run-time T(n) for all n. The growth rate of T(n) <= the growth rate of f(n).
Definition: T(n) is O(f(n)) iff (if and only if) there exist positive constants c and n0 such that T(n) <= c f(n), for all n >= n0.
To calculate the big-O worst case run-time of an algorithm:
1. Count each step (primitive operation) and come up with a polynomial (or exponential) in terms of the input size n.
2. Take highest order term with n in it in the polynomial in step 1 and drop its leading coefficient to get f(n) in O(f(n)).
Examples:
· T(n) = 3n + 2 is O(n) since 3n + 2 <= 4n for all n >= 2 where c=4 and n1 = 2.
T(n) = 10n^2 + 4n + 2 is O(n^2) since 10n^2 + 4n + 2 <= 11n^2 for all n >= 5 where c=4 and n1 = 2.

[/tag]

Code:

r = 0 
for i = 1 to N-1 do 
for j = i+1 to N do 
for k = 1 to j do 
r = r+1;

Code:

r = 0
for i = 1 to N-1 do
    for j = i+1 to N do
        for k = 1 to j do
            r = r+1;

Isn't this simply O(N^3) because there are three approx. N-loops?

Yes, I believe you are right. Thanks