Jump to content
  • Advertisement
Sign in to follow this  
RavNaz

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.

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:




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 this post


Link to post
Share on other sites
Advertisement
It is impossible to say when we know nothing about "something" and "something else".
What is n?

Share this post


Link to post
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 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
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 this post


Link to 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 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(iLength[sup]2[/sup]), but since iLength 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:

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 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 :


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)?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!