How is the run time calculated in this insertion sort algorithm?

Question

I am looking at this algorithm in CLRS page 26:

I am a novice when it comes to these things so please make your explanations as simple as possible.

For the cost column, does c1, c2, c4, etc denote a value the same way n does, or are they just labels? My understanding is an operation takes one time unit (such as j=2 is an operation that writes something once, therefore its one time unit) so does c1 mean one time unit?

Secondly, why does key=A[j] happen n-1 times?

Thirdly, line 3 is a comment therefore does not have an execution, so why does it happen n-1 times?

Answer 1

One question at a time:

To answer your first question: $c_1, c_2, c_4, c_5$ etc. are all costs. You can also look at them as constant time, or $O(1)$ operations. In practice, the value of these costs themselves get absorbed with really big $n$ and are not considered when calculating asymptotic runtime. So for instance, when calculating the total runtime, we eventually upper bound all constants into a single constant, say $C$. But $c_1, c_2, c_4$, etc. are there to help you understand the process of how the algorithm actually works. The more important part is how many times each step occurs. The constant is there to tell you that each operation takes place in constant time, and is obviously not dependent on the input size (meaning it doesn't have any $n$ associated with it). Now every line has some number of operations - that's given by a function of $n$ in the right column. Your total runtime is just the sum of the runtimes of each step $i$, which in turn is some constant, $c_i$ multiplied by the number of times the operation is repeated. I hope that helped give you some clarity about how runtime actually works.

Now regarding your second question: Note carefully that the array goes from 2 to $n$. So number of iterations is $n-2+1=n-1.$

I think you're a bit confused about what contributes to the total runtime: Remember that line can be executed how many ever times, but its contribution to the total runtime is just its cost times the number of times it occurs. As it's commented, the cost is 0 so it does not contribute to the total runtime.

Answer 2

Let me answer step by step:

1. $c_1, c_2, c_4$ etc. are costs of the operation in the corresponding line. For example $c_1$ is the cost of for: one pass of this line costs $c_1$.
2. $key=A[j]$ happens $n-1$ times, because we start from $2$ and $n=A.\text{length}$.
3. As it is commented, its cost is $0$.