ML Interview Q Series: Which popular algorithms from everyday usage have constant-time, logarithmic-time, and linearithmic-time complexities?

Mar 23, 2025

📚 Browse the full ML Interview series here.

Comprehensive Explanation

Time complexity helps assess how the runtime or resource usage of an algorithm grows in relation to the input size. Here we explore some commonly encountered algorithms and routines that exhibit constant, logarithmic, or linearithmic time complexities in daily situations.

Connect with me on X (Twitter)

Constant Time Complexity

A routine with constant time complexity does the same amount of work regardless of the input size. This implies that the runtime does not change even if the input grows large.

Accessing an element in an array by its index is a representative example. Another instance is checking the size of a fixed-size structure maintained alongside a counter in some data structures. Hash table lookups (assuming a low collision scenario) are typically treated as constant time as well.

When you launch a messaging application on your phone and it fetches your profile picture from a direct index in memory, it is often performing an O(1) operation for that lookup. Similarly, toggling Wi-Fi on or off is simply flipping a boolean state in the operating system, which is also constant time.

Logarithmic Time Complexity

Algorithms that halve the input space at each step generally operate in O(log n) time. A classic example is binary search on a sorted array. Whenever you perform a search in a well-structured data set—such as looking for words in a dictionary or searching for data in a balanced binary tree—it typically takes logarithmic time.

In daily scenarios, searching for a friend’s contact in an alphabetically sorted phone book app or sifting through a sorted list of emails by a specific sender is often akin to a binary search. If the phone's software uses balanced binary search trees or efficient indexing structures to store contact lists, each contact lookup is approximately O(log n).

Linearithmic Time Complexity

Linearithmic complexity is common in efficient sorting algorithms. One of the best-known examples is mergesort, which divides the array into smaller halves, recursively sorts each half, and then merges them back together. Quicksort and heapsort also often exhibit similar time complexity, especially in average or typical scenarios.

Any time you sort your files by date or name on your computer, or you rely on an application (like a photo app) sorting your images by metadata in the background, these sorts of routines generally use sorting algorithms with O(n log n) complexity. This is so fundamental that you often see O(n log n) routines whenever you rearrange or sort large datasets in day-to-day applications.

Practical Code Example

Below is a minimal Python snippet demonstrating how one might compare the different complexities in code. Although contrived, it outlines a constant-time element access, a binary search, and a mergesort example:

def constant_lookup(my_list, index):
    # O(1) access by index
    return my_list[index]

def binary_search(sorted_list, target):
    # O(log n) search for a target in a sorted list
    low = 0
    high = len(sorted_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def merge_sort(arr):
    # O(n log n) mergesort
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

Common Pitfalls and Practical Considerations

An often overlooked aspect is that theoretical complexities can differ from real-world performance due to constant factors and hardware constraints. A hash-based lookup can become worse than O(1) if collisions are not handled well or if the hash table is poorly sized. Similarly, mergesort’s O(n log n) factor can be overshadowed by memory constraints if the data does not fit into cache. Balanced tree searches in a real implementation can degrade toward O(n) if the tree becomes unbalanced.

Another point to note is that libraries in different languages may implement sorting or searching methods differently, but the typical complexities remain O(log n) for binary search type algorithms and O(n log n) for sorting, assuming average or typical cases. In pathological scenarios, quicksort can degrade to O(n^2) if the pivot selection is unfortunate and no additional measures are taken to prevent it.

Follow-up Questions

Could you explain how a hash table achieves constant-time lookups in practice?

Hash tables rely on a hash function mapping input keys to indices in a table. If the hash function distributes keys evenly, collisions are minimized, so looking up an item is often a single indexing operation (constant time). In the event of a collision, a resolution strategy is employed, such as chaining or open addressing. Under worst-case scenarios where every key ends up in the same bucket, lookups can degrade toward linear time, but in practice, good hashing techniques and table resizing ensure that collisions remain rare.

What are the trade-offs between binary search trees and hash tables for lookups?

Hash tables can yield faster average lookups (O(1)) if collisions are rare. However, they require a good hash function and might waste memory if the load factor is not optimized. Balanced binary search trees, on the other hand, maintain a sorted structure, providing O(log n) average lookups, but they also allow for efficient ordered operations like range queries. If the data is dynamic, maintaining a balanced tree can be more complex, whereas hash tables only need to handle collisions. In real systems, the choice depends on the need for sorted traversal, memory constraints, and the expected distribution of keys.

What happens if mergesort is used on a linked list?

If mergesort is implemented on arrays, dividing the data usually takes constant or O(1) time to compute indices, but splitting can be O(n) if we physically partition an array. Merging can be O(n) because each element is copied once. For a linked list, mergesort can still be performed, but the split step might need to traverse the list to find the midpoint, which adds an extra O(n) overhead. Merging two sorted linked lists can be done in O(n) without extra space if you manipulate the pointers carefully. Thus, mergesort on linked lists remains O(n log n) in total time, but with certain implementation nuances.

How could real-world factors affect binary search’s performance?

Binary search assumes random access memory, where accessing the middle element can be done instantly by index. On hierarchical storage (like disk-based systems), accessing a middle element may incur additional I/O overhead. Caching effects can mean that contiguous accesses in a linear scan might sometimes outperform repeated random index lookups if the data is large or scattered. Also, if the data is not sorted or the index is not built correctly, binary search is not applicable. In distributed systems, network latency can overshadow the theoretical gain of a logarithmic algorithm.

In which scenarios might a simple linear search be faster than binary search?

If the dataset is extremely small or if the cost of comparing elements is negligible, a linear search might be competitive and sometimes faster due to lower constant factors. Additionally, if the data is already in CPU cache or stored contiguously in a small array, a loop with no overhead can sometimes beat the overhead of calculating midpoints and performing jumps in memory. That said, for medium to large data sizes, a well-implemented binary search typically outperforms linear searches.

How can we optimize O(n log n) sorting in practice?

Modern libraries often use hybrid sorting algorithms that switch to insertion sort for very small subarrays, because insertion sort has lower overhead for such cases. They also optimize mergesort or quicksort to reduce the number of function calls, handle repeated elements efficiently, and leverage prefetching of memory. Some specialized sorts—like counting sort or radix sort—can outdo O(n log n) under certain constraints (e.g., when the range of keys is limited or when the data size is known in advance).

These considerations highlight how time complexity alone might not paint the full performance picture, but it remains a vital theoretical framework for algorithm design and analysis.

Below are additional follow-up questions

How do we reconcile best, average, and worst-case complexities for a given algorithm, and why is it important in practice?

In theory, an algorithm like quicksort can have a best-case complexity of O(n log n), an average-case complexity of O(n log n), and a worst-case complexity of O(n^2). The same is true for other algorithms that may have a big gap between average-case and worst-case. In practice, engineers are often more concerned with average performance because real-world data distributions rarely force them into worst-case scenarios. However, if you unexpectedly encounter an input that triggers the worst-case pattern—like a nearly sorted array in naive quicksort—performance can degrade significantly.

To handle such scenarios, many implementations use randomization or pivot selection strategies (e.g., median-of-three) to reduce the chance of pathological pivot choices. Some libraries even switch to a different algorithm mid-execution if they detect that the input is forcing worst-case conditions. Consequently, understanding all three cases (best, average, worst) helps you make robust engineering decisions rather than only relying on a single theoretical complexity number.