Time Complexity | Engineering Interview Kit

Concept

When writing an algorithm, it’s not enough to ask “Does it work?”. You must ask “How long will it take if I give it 10 million items?”

Time Complexity is a mathematical way of describing how the runtime of an algorithm increases as the size of the input data ( $N$ ) increases. We measure this not in exact seconds (because a supercomputer is faster than a laptop), but in operations performed.

Mental Model

Think of searching for a phone number in a physical phone book.

Bad Algorithm ( $O(N)$ ): You flip to page 1, check every name. Flip to page 2, check every name. If there are 1,000,000 pages, it takes you 1,000,000 steps. As the book gets bigger, the time required scales linearly.
Good Algorithm ( $O(\log N)$ ): You open exactly to the middle. If the name you want comes before the middle, you rip the book in half, throw away the back half, and repeat. Even if the book has 1,000,000 pages, you find the name in about 20 steps.

Common Time Complexities

From best to worst:

$O(1)$ - Constant Time: The operation takes the exact same amount of time, regardless of the data size. (e.g., Looking up a value in a Hash Map, reading the first item of an array).
$O(\log N)$ - Logarithmic Time: The dataset is repeatedly halved. (e.g., Binary Search).
$O(N)$ - Linear Time: You must look at every single item once. (e.g., Looping through an array).
$O(N \log N)$ - Linearithmic Time: Standard for highly optimized sorting algorithms. (e.g., Merge Sort, Quick Sort).
$O(N^2)$ - Quadratic Time: For every item, you must loop through every other item. Usually the result of nested for loops. (e.g., Bubble Sort, checking every pair in an array).
$O(2^N)$ - Exponential Time: The operations double with every new item. This will crash your computer if $N > 40$ . (e.g., Naive recursive Fibonacci, finding all subsets).
$O(N!)$ - Factorial Time: The worst possible complexity. Finding all permutations of a string.

Calculating Time Complexity

To calculate it in code, follow three simple rules:

Drop Constants: $O(2N)$ becomes $O(N)$ . $O(N / 2)$ becomes $O(N)$ .
Drop Non-Dominant Terms: $O(N^2 + N + 100)$ becomes $O(N^2)$ . The fastest growing term dominates at infinity.
Add vs Multiply: If you do loop A then loop B, you add them: $O(A + B)$ . If you do loop A inside loop B, you multiply them: $O(A \times B)$ .

// Example: Calculating Complexity
function findMatch(arrayA: number[], arrayB: number[]) {
    // 1. O(A) operation
    for (let i = 0; i < arrayA.length; i++) {
        console.log(arrayA[i]); 
    }

    // 2. O(B * B) operation (Nested Loops)
    for (let i = 0; i < arrayB.length; i++) {
        for (let j = 0; j < arrayB.length; j++) {
            console.log(arrayB[i], arrayB[j]);
        }
    }
}
// Final Time Complexity: O(A + B^2)

Interview Questions

Q: If an algorithm has a Time Complexity of $O(N^2)$ , what happens to the runtime if you double the input size?
A: The runtime increases by a factor of 4. ( $O((2N)^2) = 4N^2$ ). If an array of 10,000 items takes 1 second, an array of 20,000 items will take 4 seconds.

Q: A developer says: “My algorithm is $O(100N)$ because it loops through the array 100 times, which is worse than $O(N^2)$ for small inputs.” Are they right?
A: Yes, for very small inputs, $100N$ might take longer than $N^2$ . However, Big-O notation explicitly evaluates the behavior as $N \rightarrow \infty$ (approaches infinity). At $N = 101$ , $N^2$ (10,201 operations) overtakes $100N$ (10,100 operations) and will forever remain mathematically slower. Therefore, $O(100N)$ is fundamentally classified as $O(N)$ , which is a vastly superior algorithm to $O(N^2)$ .