Big O Notation and the Climb Over Constants.

I was recently going through the implementations and complexities of common sorting algorithms such as Quicksort and Mergesort. I noticed that many programmers, including myself, often ignore the constant factors when calculating time complexity. This is typically acceptable for a high-level analysis, but there are situations where this oversight can lead to misunderstandings about the efficiency of algorithms.

To illustrate, both Quicksort and Mergesort have an average time complexity of O(n logn). Mergesort consistently achieves this complexity in all cases, making it reliable and predictable. Quicksort, on the other hand, has a worst-case time complexity of O(n²), which occurs when the pivot selection leads to highly unbalanced partitions. In these scenarios, Quicksort can perform as poorly as simple algorithms like Selection Sort. However, Quicksort is still generally considered more efficient in practice because it has an average-case time complexity of O(n logn) and tends to be faster due to its lower constant factors.

This leads to a critical question: If Quicksort has a worst-case time complexity of O(n²) and Mergesort consistently performs at O(n logn), why is Quicksort often preferred? Isn't Mergesort inherently faster?

Let's break it down. Suppose you have this simple function to print every item in an array.

void printItem1(vector<int> &arr) {

ㅤㅤ    for (int i = 0; i < arr.size(); i++) {

ㅤㅤ        ㅤcout << arr[i] << " ";

ㅤ ㅤ   }

}

This function goes through every item in the array and prints it out. Because its iterates over the whole array once, this function runs in O(n) time. Now suppose you change this function so it sleeps for 1 second before it prints out and item:

#include <thread> // For sleep functionality

#include <chrono> // For specifying time duration

void printItem2(vector<int> &arr) {

ㅤㅤ    for (int i = 0; i < arr.size(); i++) {

ㅤㅤㅤㅤ        this_thread::sleep_for(chrono::seconds(1)); // Sleep for 1 second

ㅤㅤㅤㅤ        cout << arr[i] << " ";

ㅤㅤ    }

}

Before it prints out an item, it will pause for 1 second. Suppose you

print an array of five items using both functions.

[1, 2, 3, 4, 5]

printItem1: 1 2 3 4 5

printItem2: <sleep> 1 <sleep> 2 <sleep> 3 <sleep> 4 <sleep> 5

Both functions loop through the list once, so they're both O(n) time.

Which one do you think will be faster in practice? I think printItem1

will be much faster because it doesn't pause for 1 second before printing

an item. So even though both functions are the same speed in Big O

notation, printItems1 is faster in practice. When you write Big O

notation like O(n), it really means this,

C * n, ㅤwhere n = some amount of time.

C is some fixed amount of time that your algorithm takes. It's called the

constant. For example, it might be 10 milliseconds * n for printItem1 versus 1 second * n for printItem2.

We usually ignore that constant, because if two algorithms have

different Big O times, the constant doesn't matter. Take binary search

and simple search, for example. Suppose both algorithms had these

constants.

10ms * n for simple search

1 sec * log n for binary search

We might say, "Wow! Simple search has a constant of 10 milliseconds,

but binary search has a constant of 1 second. Simple search is way

faster!" Now suppose you're searching a list of 1 billion elements. Here

are the times.

simple search | ㅤ10ms * 1 billion = 116 days

binary search | ㅤ1s * 1 billion = 30 seconds

As you can see, binary search is still way faster. That constant didn't

make a difference at all.

But sometimes the constant can make a difference. Quicksort versus

merge sort is one example. Quicksort has a smaller constant than

merge sort. So if they're both O(n log n) time, quicksort is faster. And

quicksort is faster in practice because it hits the average case way more

often than the worst case.