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;
This is a discussion on Big-O analysis within the C++ Programming forums, part of the General Programming Boards category; What is the Big-O analysis of this code? I think the code is doing a sort but I'm confused. Is ...
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;
i got a few questions one is that in a loop two i think im gonna need more of the code to figure it out might just be me but the r = 0 and then the r = r + 1; should mean its in a loop cause r would be a counter the for stuff i would have to know what n and n-1 is basicly yeh ill need a bigger peice of code to work from to figure this out for yeh.
Simple Programming
:::: Error Message != A Smile ::::
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 know i might sound like a newbie but i gotta ask what exactly is the big-O?
Simple Programming
:::: Error Message != A Smile ::::
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;
Isn't this simply O(N^3) because there are three approx. N-loops?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;
Yes, I believe you are right. Thanks