r/AskComputerScience

Hey guys. I'm supplementing my DSA course at Uni with CLRS, and I'm a little confused about the following paragraph discussing the reasoning behind Insertion-Sort having an upper bound of O(n²):

"The running time is dominated by the inner loop. Because each of the (n - 1) iterations of the outer loop causes the inner loop to iterate at most (i - 1) times, and because i is at most n, the total number of iterations of the inner loop is at most (n - 1)(n - 1)." (this is page 52 of the 4th edition)

Here is the pseudocode:

Insertion-Sort(A, n)
     for i = 2 to n
          key = A[i]
           j = i - 1
          while j > 0 and A[j] > key
               A[j + 1] = A[j]
               j--
         A[j + 1] = key

It is true that the outer loop of the insertion sort pseudocode in CLRS runs (n - 1) times regardless of the problem instance, and that at most, the inner while loop executes (i - 1) times for each iteration.

However, I'm confused about why the author states that the inner while loop runs at most (n-1)(n-1) times. The inner while loop only has the opportunity to execute (n - 1) times when i assumes the value of n, which of course only occurs once during the last iteration, not every (n - 1) iterations.

Wouldn't the number of iterations of the inner while loop be determined by the summation 1 + 2 + 3 + ... + (n - 1) = n(n - 1) / 2 ?

In either case, the O(n²) upper bound is correct, but I need some clarity on the author's reasoning, as I don't seem to be following it.

For those who are genuinely good at coding now, was there a specific realization, habit, or shift in thinking that made things click for you? Not talking about grinding endlessly, but that moment where code started making sense and patterns became obvious. Was it how you practiced, how you learned fundamentals, how you debugged, or how you thought about problems? I’m curious what separated I’m struggling from I get this now

Can i study Computer systems a programmers perspective book without C programming language?