Running Time Analysis for Iterative sorting algorithm

Question

I'm learning how to write theoretical analysis for the running time of algorithms and I am wondering if it's correct to say for the following code:

while(high >= low) {
     loop body here....
     high--;
     low++;
}

Where low begins at index 0, and high begins at index N - 1, for an array of N integers. The loop body will run (n / 2) times, or it will make (n / 2) + 1 comparisons. Is it correct to say this? And if so, to get the complete run time analysis for the whole function, would you then evaluate any inner loops to create a complete function for the run time?

Of course the inner functions are needed for a complete analysis of this function. Your outer loop will be in O(n), but if your inner function is non-constant, the complete analysis will be worse than O(n) / (I'm ignoring constants. In your case: i'm ignoring n/2). — sascha
– sascha, Commented Oct 5, 2015 at 0:07
Yah it's O(n) but am I right in my thinking prior to eliminating the constants? — coopwatts
– coopwatts, Commented Oct 5, 2015 at 0:10

displayName · Accepted Answer · 2015-10-05 00:37:08Z

1

In the code section called loop body here..... of your code, you may have some other loop running with a complexity of some f(n). The given while loop is going to run n / 2 times if n is even and (n / 2) + 1 times if n is odd.

So, the running time complexity of outer loop would be simply O(n / 2) = O(n).

Now,

if the loop body here..... code section is fiddling with high and/or low, then the complexity of this while loop will vary.
if the loop body here..... code section is O(1) and it doesn't modify high and/or low, then the overall run-time is O(n).
if the loop body here..... code section is O(n) and it doesn't modify high and/or low, then the overall run-time is O(n²).
In general, if the loop body here..... code section is O(f(n)) and it doesn't modify high and/or low, then the overall run-time is O(n * f(n)).

edited Oct 5, 2015 at 0:37

answered Oct 5, 2015 at 0:18

displayName

14.4k9 gold badges65 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

coopwatts Over a year ago

So if high and low are only being used for comparisons and index position, but the values aren't being changed then the complexity would be O(n^2) correct?

displayName Over a year ago

@cwattsdis: Nope. The complexity will be O(n). See the second bullet.

coopwatts Over a year ago

But if it was a for loop inside the while loop that runs n - 1 times then it would be O(n^2) right?

displayName Over a year ago

@cwattsdis: Happy to do so.

coopwatts Over a year ago

Let us continue this discussion in chat.

|

Collectives™ on Stack Overflow

Running Time Analysis for Iterative sorting algorithm

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related