Constant,
linear, quadratic, logarithmic or linearithmic are terms that vaguely describe the worst case runtime of algorithms in CSC148 but they are not precise enough in CSC165. We need the exact number of steps. This calls for
some nice mathematical toys, which we introduce with the following algorithm:
def mystery_sort(L: list):
“””
Sort the elements of L in mysterious
order.
“””
n = len(L)
outer_index = 1
while outer_index < n:
value = L[outer_index]
inner_index = outer_index
while inner_index > 0 and
A[inner_index – 1] < value:
A[inner_index] = A[inner_index
– 1]
inner_index = inner_index – 1
A[inner_index]
= value
outer_index = outer_index + 1
Since mystery_sort has a nested loop with monotone loop indexes, then its worst-case runtime is quadratic. What is less obvious is the exact number of
steps that it takes for mystery_sort to run in the worst case. Our procedure to count mystery_sort is as
follows:
(1) Assume that each line represents one step to make the analysis easier.
(2) Count from the inner loop to the outer loop.
(3) Add up the steps that are outside the outer loop.
So assume (1). Then do (2) and (3).
(1) Assume that each line represents one step to make the analysis easier.
(2) Count from the inner loop to the outer loop.
(3) Add up the steps that are outside the outer loop.
So assume (1). Then do (2) and (3).
Inner Loop
To count the
steps of the inner loop, our first mathematical toy comes into play: abstraction. It helps us determine the number of times that
the inner loop executes. Observe that
the inner loop depends on the outer_index.
However, the outer_index is not concrete since it changes each time the
outer loop executes. So we must think
abstractly; use an arbitrary integer $i$ to represent the outer_index. Then $i$ becomes the number of times
that the inner loop executes. Now the easy
part: the inner loop performs three steps for each iteration. Since the inner loop executes $i$ times, then
the number of steps of the inner loop is $3i$.
Outer Loop
In addition to the number of steps of the inner loop, we
have the following steps inside each outer loop:
(1) while
outer_index < n
(2) value
= L[outer_index]
(3) inner_index
= outer_index
(4) loop
guard of the inner loop
(5) A[inner_index]
= value
(6) outer_index
= outer_index + 1
This is $6$ steps in total.
Add it to the steps of the inner loop and you see that each iteration of
the outer loop executes $3i + 5$ steps.
We still have to add up the steps for each iteration so here our second
mathematical toy comes into play: summation. Since the outer loop runs $n - 1$ times, then
the total steps of the outer loop is the following summation:
\[\sum_{i = 1}^{n -
1} (3i + 6)\].
To find the
sum of this series, our mathematical final toy comes and it is Euler’s trick. This is a technique for finding the sum of an arithmetic series. First decompose the
summation:
\[\sum_{i = 1}^{n -
1} (3i + 6) = 3 \sum_{i = 1}^{n - 1} i + \sum_{i = 1}^{n - 1} 6\]
Then perform the following calculation:
\[\sum_{i = 1}^{n -
1} i = 1 + 2 + 3 + … + (n - 3) + (n - 2) + (n - 1) =\]
\[\frac{1}{2}(1 + 2 +
3 + … + (n - 3) + (n - 2) + (n - 1) + \]
\[(n - 1) + (n - 2) +
(n - 3) + … + 3 + 2 + 1) =\]
\[\frac{n(n - 1)}{2}
= \frac{n^2 - n}{2}\]
Substitute back into the series and we get the number of steps that outer loop executes:
\[\frac{3n^2 - 3n + 12n - 12}{2} = \]
\[\frac{3n^2 - 9n - 12}{2}\]
Outside Both Loops
There are still the following steps to
consider:
(1) n = len(L)
(2) outer_index = 1
(3) loop guard of the outer loop
This is $3$ steps so the total number of steps that the algorithm
performs is:
\[\frac{3n^2 - 9n - 6}{2}\]
