# two O(n) in a row?

This topic is 2699 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:

 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++; } } 

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 something else condition. In the extreme cases, if it is never true, the algorithm will never end, and if it is true as soon as iCtr >= iLength, 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.

 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++; } } 

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(iLength[sup]2[/sup]), but since iLength is constant, its running time is also constant.

##### Share on other sites
Your second loop is overly complicated. It can be written as this:
 for(int i = 0 ; i <= length ; ++i) { SomeFunc1(i); } done = true; 
"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 :

 for ( int i = 0 ; i < 5 ; i++ ) { for ( int j = 0 ; j < 5 ; i++ ) { for( int k = 0 ; k < 5 ; i++ ) { } } } 

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

 for ( int i = 0 ; i < 5 ; i++ ) { for ( int j = 0 ; j < 5 ; i++ ) { } for( int k = 0 ; k < 5 ; i++ ) { } } 

Is that then O(n-squared)?

1. 1
Rutin
19
2. 2
3. 3
JoeJ
16
4. 4
5. 5

• 26
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001782
×