Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1?
for j = 0 to m-1 do
b[j] = 0
for i = 0 to n-1 do
b[S[i]] = b[S[i]] + 1
i = 0
for j = 0 to m-1 do
for r = 1 to b[j] do
S[i] = j
i = i + 1
I already understand that the algorithm does in fact correctly sort the array S. In terms of the runtime, I am not so sure. From what I've learned, I came up with $O(n*m)$. I know that the time complexity of the first loop is $O(m)$. The time complexity of the second loop is $O(n)$. As for the third loop, this is where I get a little confused. I figured that the summation would be $\sum_{j=1}^{m}\sum_{r=1}^{n}c$, where c is some constant. I got this because the outer loop starts at 0 and goes to m-1 (this can be re-written as 1 to m). Then, from tracing and intuition, I figured the inner loop would have to start at 1 and go to n. Depending on the number of elements in the array, this is the number of times the inner loop executes and performs the constant time statements.
So, solving the summation a little, I get $\sum_{j=1}^{m}nc$, which simplifies to $cmn$. Thus, I got $O(n*m)$ + $O(n)$ + $O(m)$, which would have a worse case of $O(n*m)$. Any thoughts on this?
The time complexity of the third loop can be bounded more tight. You already observed that the outer loop is executed exactly $m$ times. For each $j$ the inner loop is executed $b[j]$ times. Thus, the time complexity for the third loop can be expressed as \begin{align*} \sum_{j=0}^{m-1} c \cdot b[j] = c \cdot \sum_{j=0}^{m-1} b[j]. \end{align*} Since the second loop (in which the values of the $b[j]$ are set) is executed exactly $n$ times, the sum over all $b[j]$ will also be exactly $n$. Thus, the complexity of the third loop can be further simplified to \begin{align*} c \cdot \sum_{j=0}^{m-1} b[j] = c \cdot n \end{align*} which results in a total time complexity of $\mathcal{O}(n+m)$ for the algorithm.