What do the constant factors in a time complexity equation represent?

Question

all.

I'm taking a Coursera course on data structures and algorithms to prep myself for my upcoming semester which has a data structures and algorithms course. In my study I'm currently on the topic of algorithm analysis. This lead to me going down a rabbit hole and reading other resources. In one of those resources they have a time complexity equation for Insertion-Sort:

My question is what exactly do the constant factors in the equation (C_1, C_2, C_3, etc.) represent? My understanding is they represent the run time to execute a specific line (so C_2 represents the time it takes to execute key = A[j]. This is based on the understanding that the equation represents time complexity, and time complexity is a measurement of the change in runtime as input size changes (Figure 2 and Figure 3 below):

Of course, you can see in the same sentence the authors of Introduction to Algorithms say C_i is a measurement of steps. Then in the book A Common-Sense Guide to Data Structures and Algorithms, Second Edition the author says this:

If you take away just one thing from this book, let it be this: when we measure how “fast” an operation takes, we do not refer to how fast the operation takes in terms of pure time, but instead in how many steps it takes. We’ve actually seen this earlier in the context of printing the even numbers from 2 to 100. The second version of that function was faster because it took half as many steps as the first version did.

Why do we measure code’s speed in terms of steps? We do this because we can never say definitively that any operation takes, say, five seconds. While a piece of code may take five seconds on a particular computer, that same piece of code may take longer on an older piece of hardware. For that matter, that same code might run much faster on the supercomputers of tomorrow. Measuring the speed of an operation in terms of time is undependable, since the time will always change depending on the hardware it is run on.

However, we can measure the speed of an operation in terms of how many computational steps it takes. If Operation A takes 5 steps, and Operation B takes 500 steps, we can assume that Operation A will always be faster than Operation B on all pieces of hardware. Measuring the number of steps is, therefore, the key to analyzing the speed of an operation.

Measuring the speed of an operation is also known as measuring its time complexity. Throughout this book, I’ll use the terms speed, time complexity, efficiency, performance, and runtime interchangeably. They all refer to the number of steps a given operation takes.

The Wikipedia page for Time Complexity says:

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

So there seems to be a dual definition and understanding of time complexity and what the equation represents. I see that intrinsically, the more steps an algorithm takes the longer it's going to take. I also understand that it's usually very difficult or impossible to measure the exact running time of an algorithm and therefor may be efficacious to count the number of steps an algorithm takes.

That said, I'm having a difficult time fulling making this connection between the two, and ultimately what those constant factors in the equation represent. If they do represent running time, why are they then counted as just a constant and seem to be counted as 1 (1 for each time the line is executed)?

Hoping someone out there can help me understand what the equation represents, the connection between runtime and steps, etc.

I appreciate you taking the time to read this and for your help.

Answer 1

Because they are just...constants! They represent the specific time each operation on average takes to be executed (consider that in reality every operation is a set of operations in Machine code), so every different operation has a different running time but if the constants are all of similar sizes the difference between them is not always that important (every programming languages has his features so something really fast in one can be somewhat slow in another, here for example there are performanceTips for python).

The focus of the analysis is on how many times the operations are executed. Big O complexity considers the limiting behaviour so constants are not important, just the 'speed' of the functions involved ( a*n^2+b*n is always O(n^2) for every constants a and b).

Anyway some optimization can be useless because the different operations used cost more. Some instead can be really important if the two operations have constants with a big difference in execution time

Answer 2

I think the constants represent the steps that must be taken to execute each line. The equation represents the number of all steps.