Mathematical tools used to analyze the performance of algorithms by understanding how their efficiency changes as the input size grows.
Read this page on Big(O) notation.
GeeksForGeeks
A discussion: An algorithm can be assessed based on the following three criteria:
The statement “Runtime complexity indicates how much time a particular algorithm will take for a given input size” is generally accurate. It’s similar to asking a travel agent how long it takes to get from Chandigarh to Delhi, and receiving an answer of 5 hours. Based on this, you can plan your travel, assuming it will take 5 hours. This is a useful approximation but doesn’t measure the distance directly.
If you’re considering different modes of transportation or potential delays like traffic or tolls, this estimation might not be sufficient. The more precise measure would be the distance between Chandigarh and Delhi, which is 250 km. From this, you can calculate travel time based on your mode of transport and other factors, such as speed—if you travel at an average speed of 50 km/hr, the journey would indeed take 5 hours.
Similarly, for an algorithm, if it requires 2.5 * 10^9 instructions (units of work) and is running on a machine with a computational power of 2.5 GHz, it would take approximately 1 second to execute (assuming no other delays, and the operating system handles the task without interruptions).
Therefore, runtime complexity can be more accurately defined as the number of instructions an algorithm sends to the CPU for a given input. The execution time depends on the CPU’s speed and how the operating system schedules the task.
In Big O notation, O(n) represents that for an input size of n, the algorithm should execute around K*n + C instructions, where K and C are constants.
Just as runtime complexity indicates how long an algorithm will take, space complexity describes how much additional RAM is needed to execute the algorithm. For example, merge sort has a space complexity of O(n), meaning it requires an additional 1GB of RAM to sort 1GB of data.
Consider the following two points:
The CPU relies on cache for computations. When adding two numbers, a and b, both values must be in the cache. If they are already present, it’s a cache hit; if not, it’s a cache miss, and the OS will need to transfer the values from RAM to the cache.
Since reading from memory is approximately 1000 times slower than reading from cache, the OS aims to maximize cache hits and minimize cache misses.
Algorithms that access data randomly may lead to more cache misses compared to those that access data sequentially. For instance, if you declare an array of size 100 and access only the element at index 0, the OS might preload elements a[1], a[2], a[3], and a[4] into the cache, assuming you’ll likely request them next. If you then request a[5], a cache miss occurs, and the OS will evict some of the cached elements to load a[5] through a[9].
In this scenario, an algorithm performing sequential access could result in about 20 cache misses (and 20 reads from RAM), whereas an algorithm with random access might experience 100 cache misses.
Typically, runtime complexity is prioritized over other factors because cache misses are relatively inexpensive and RAM is quite affordable nowadays. For instance, if a new algorithm can make Google Search faster but requires an additional 16GB of RAM, Google would likely be willing to invest in that extra memory. However, if I need to choose between insertion sort and merge sort for a smartwatch with very limited memory, I would opt for insertion sort, as the O(n) space complexity of merge sort could potentially crash the device.
When two algorithms have the same runtime and space complexities, I would then select the one that is more cache-friendly.