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?
`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.
Get Answers For Free
Most questions answered within 1 hours.