Sign in to follow this  

two O(n) in a row?

This topic is 2489 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone,

if I've got something like the following:


[code]

void SomeFunc1( int iNum )
{
for ( int i = 0 ; i < (iNum/2) ; i++ )
{

}
}

void main( void )
{
int iLength = 5;
SomeFunc1( iLength ); // executes in O(n);


int iCtr = 0;
while( bDone == false )
{
if ( iCtr < iLength )
{
SomeFunc1(iCtr);
}
else if ( something else )
{
SomeFunc1(iCtr);
bDone = true;
}
iCtr++;
}
}
[/code]

using Big O, what would this be?

I have what appears to be O(n) with the somefunc1 function, followed by the while loop that I guess effectively means I have a nested loop with the SomeFunc1 being called inside... so overall I would say this algorithm was O(n-squared).... is that right?

Share this post


Link to post
Share on other sites
The running time is still depending on the [i]something else[/i] condition. In the extreme cases, if it is never true, the algorithm will never end, and if it is true as soon as [i]iCtr[/i] >= [i]iLength[/i], the algorithm is O(1).

Share this post


Link to post
Share on other sites
Hi,

i saw the post before u changed it and it was a lot clearer in my opinion. Now you have an if(x), else if(y) and no else. I can't see a reason for a loop of that kind.

Anyways, if u have a function with runtime O(n) and you call it x times, where x is not a constant number you have O(x*n). If you call the function as long as a certain condition is not met, the x might be not determined and you have to look whats the worst case, i.e. the maximum number of calls (maybe its not finite if the condition is never met).

Share this post


Link to post
Share on other sites
OK.

[code]

void SomeFunc1( int iNum )
{
for ( int i = 0 ; i < (iNum/2) ; i++ )
{

}
}

void main( void )
{
int iLength = 5;
SomeFunc1( iLength ); // executes in O(n);


int iCtr = 0;
while( bDone == false )
{
if ( iCtr < iLength )
{
SomeFunc1(iCtr);
}
else
{
SomeFunc1(iCtr);
bDone = true;
}
iCtr++;
}
}
[/code]

Not sure if this helps...

Big O looks at worst case, so in the while..for nest I have above, given then iLength would be fixed, that is O(n-squared) right?

Share this post


Link to post
Share on other sites
In that case, the while-loop is actually O(1), because there are no varying factors to compare the running times against. It is, however, O([i]iLength[/i][sup]2[/sup]), but since [i]iLength[/i] is constant, its running time is also constant.

Share this post


Link to post
Share on other sites
Your second loop is overly complicated. It can be written as this:
[code]
for(int i = 0 ; i <= length ; ++i)
{
SomeFunc1(i);
}
done = true;
[/code]
"done" could be removed if it was a local variable only used for controlling the loop.

This might help simplify your reasoning. This is very different from your original code with the unknown condition though. Make sure you are measuring the algorithm you implemented and not a lookalike with different performance characteristics.

Share this post


Link to post
Share on other sites
thanks guys.

I think I'm just having trouble visualising how some of this fits together.

for example:

my understanding is that if you were to have say :

[code]
for ( int i = 0 ; i < 5 ; i++ )
{
for ( int j = 0 ; j < 5 ; i++ )
{
for( int k = 0 ; k < 5 ; i++ )
{
}
}
}
[/code]

this is O(n-cubed).... but.. how would it change if you had say:


[code]
for ( int i = 0 ; i < 5 ; i++ )
{
for ( int j = 0 ; j < 5 ; i++ )
{
}

for( int k = 0 ; k < 5 ; i++ )
{
}
}
[/code]

Is that then O(n-squared)?

Share this post


Link to post
Share on other sites
[quote name='RavNaz' timestamp='1298476846' post='4777995']
Is that then O(n-squared)?
[/quote]

As [url="http://en.wikipedia.org/wiki/Big_O_notation"]taken from Wikipedia[/url],


[quote]the big-O notation describes limiting behavior of a function when the argument tends towards a particular value or infinity[/quote]

As your "argument" is constant (5), the runtime behavior is constant (O(c*1), where c = 5*5*5 or 5*2*5, respectively). If you were to supply a variable, then the first version would indeed have O(n[sup]3[/sup]) and the second O(2*n[sup]2[/sup]) = O(n[sup]2[/sup]). Two such loops in a row would be ~O(2*n[sup]x[/sup]), where x is the factor of the dominating loop (so, if you were to put a loop with quadratic and one with cubic runtime behavior after another, the resulting behavior would be O(n[sup]3[/sup]), as [url="http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation"]the quadratic function would have neglectably small impact on overall runtime behavior as n progresses towards infinity[/url].

Share this post


Link to post
Share on other sites
In case your wondering, calling a linear time function with values of n increasing as 0,1,2,3... etc is regarded as O(n^2) because the closed form solution to the sum is:

0.5(n^2 + n). Here n^2 is the dominant term

When the running time of the inner loop is dependent on the current iteration of the outer, you have to look at the underlying progression. It's not always the case that each nested loop corresponds to an increasing power of n.

Share this post


Link to post
Share on other sites

This topic is 2489 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this