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