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

## 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 on other sites
It is impossible to say when we know nothing about "something" and "something else".
What is n?

##### Share on other sites
Updated original code.. hopefully that clears it up?

##### 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 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 on other sites
Please don't edit your posts to respond to concerns: It makes it impossible to follow the conversation. There is nothing wrong with posting an updated version of the code on a later 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 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 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 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 on other sites
Since all those loops run a constant number of times with no dependence on `n', they are technically O(1). The O notation only expresses a bound on how fast something grows as n increases.

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