Below I have an algorithm for finding the mode of a list of nondecreasing integers. I'm trying to analyze the time complexity of this algorithm.
Procedure find a mode($a_1, a_2, …, a_n$:nondecreasing integers)
modecount := 0
i := 1
while $i \leq n$
begin
value := $a_i$
count := 1
while i $\leq$ n and $a_i$ = value
begin
count := count + 1
i := i + 1
end
if count $>$ modecount then
begin
modecount := count
mode: = value
end
end
The first question I have, is how do you notice the worst case scenario without rigorously iterating through the algorithm line by line? By doing that practice, I believe i've found the worst case scenario, which is when the list is comprised of pairs of the same integers, ie. (2,2,3,3).
Next, I'm going to measure the number of comparisons used the by algorithm to analyze its time complexity. Thus, the for i = 1, we see there are 2*2 + 2 comparisons at the second while loop (that is checking conditions for $a_1$, $a_2$, and then to reject $a_3$), plus 1 comparison made at the if statement. When i = 2, there are 2*1 + 2 comparisons at the second while statement, plus 1 comparison at the if statement. When i = 3, we see there are 2*2 + 2 comparisons at the while statement, plus 1 comparisons at the if statement. Finally, when i = 4, we see there are 2*1 + 2 comparisons at the second while loop, and 1 comparison at the if statement.
In total we have, (6+1) + (4+1) + (6+1) + (4+1) = 24. We see ($4^2$) = 16, and ($4^3$) = 64. Thus, this algorithm would be O($n^3$), however the book states the algorithm is O(n). Confused, perhaps my analysis is wrong, or I'm over complicating the comparisons.
Best Answer
In a normal nested loops situation, the inner loop would execute n times for each iteration of the outer loop. So, if the outer loop executes m times, the inner loop would execute a total of m*n times.
However, in this case, both the inner and outer loops share the same loop counter i. So, we are not dealing with the case of m*n iterations.
In this case, we count the number of steps in the outer loop, count the number of steps in the inner loop and then sum them.
The outer loop has 5 assignments and 1 comparison.
So, it has 6 steps.
The outer loop executes at most n times.
So, it executes at most a total of 6n steps.
The inner loop has 2 comparisons and 2 assignments .
So, it has 4 steps.
The inner loop exexutes at most n times. So, it executes at most a total of 4n steps.
So, the procedure executes at most 6n + 4n = 10n steps.
So, total time for n integers is 10n which is O(n) since we drop the constant 10.
Note that you do not count "rejections" as an execution of a loop.