Question

Assume an array a [0 … n –1] of int, and assume the following trace:

for (int i = 0; i < n - 1; i++)

if (a [i] > a [i + 1])

System.out.println (i);

What is worstTime(n)?

Statement	Worst Case Number of Executions
i = 0	1
i < n – 1	n
i++	n - 1
a[i] > a[i+1]	n - 1
System.out.println()	n - 1

That is, worstTime(n) is: 4n – 2.

So this is part of my teachers slides. Now, my question is that why is it that the worst case number of executions for i++, a[i] > a[i+1] and System.out.println() are n-1? Shouldn't it be n-2 since the loop's stoping condition is i<n-1?

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Please note that there is a for loop in which i goes from i=0 to n-2.

Loop stopping criteria is i<n-1 but loop actually starts from 0

It should have been n-2 if the loop could have been from 1 to n-2 but it is from 0 to n-2 so, n-2+1=n-1.

A total of n-1 executions.

So, at every iteration i is incremented by 1 since its inside the loop so n-1 for it

Both a[i]>a[i+1] and print statement comes inside loop and are also executed n-1 times for each i. So, n-1 for each too.

Kindly revert for any queries

Thanks.