Understanding Time Complexity: A Guide for Beginners

When solving algorithmic problems, understanding how efficient your solution is can be crucial, especially when tackling platforms like LeetCode. This is where time complexity comes in. It helps you evaluate the performance of an algorithm in terms of how the execution time grows as the input size increases. In this blog, we’ll explore Big-O notation, common time complexities, and examples to get you started.

What is Time Complexity?
Time complexity refers to the amount of time an algorithm takes to complete as a function of the size of its input. If your algorithm works fine for small inputs but slows down as the input grows, its time complexity might not be ideal. Understanding this helps you optimize your code for large datasets, which is crucial for technical interviews and real-world applications.

Big-O Notation
We express time complexity using Big-O notation. It tells us how an algorithm's runtime grows relative to the input size, typically denoted by n.

Common time complexities you’ll come across include:

O(1) – Constant Time
The runtime does not depend on the input size. For example, accessing an element in an array by its index is an O(1) operation.

Eg:

int getElement(int arr[], int index) {
    return arr[index];  // O(1)
}

O(log n) – Logarithmic Time
This occurs when the algorithm cuts the problem size in half at each step, such as in binary search.

Eg:

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;  // O(log n)
}

O(n) – Linear Time
The algorithm's runtime grows directly proportional to the input size. A typical example is a simple loop through an array.

Eg:

int findMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal)
            maxVal = arr[i];
    }
    return maxVal;  // O(n)
}

O(n log n) – Linearithmic Time
This complexity is common in efficient sorting algorithms like Merge Sort and Quick Sort.

Eg:

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);  // O(n log n)
}

O(n^2) – Quadratic Time
The runtime grows quadratically with the input size. This is typical for algorithms with nested loops, like bubble sort.

Eg:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
        }
    }  // O(n^2)
}

O(2^n) – Exponential Time
This complexity appears in recursive algorithms where the problem branches into multiple subproblems, like the naive Fibonacci implementation.

Eg:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // O(2^n)
}

O(n!) – Factorial Time
Algorithms with this complexity grow rapidly and are generally impractical for large inputs, like the solution to the Traveling Salesman Problem and Print Permutations using brute force.

Eg:

vector<int> nums = {1, 2, 3}; // Example vector
void printPermutations(vector<int>& nums) {
    do {
        for (int num : nums) 
            cout << num << " ";
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end())); // O(!n)
}

Why Time Complexity Matters in Coding Interviews
Many LeetCode problems require you to solve them within specific time limits, often dependent on input sizes. For instance, if the input size can go up to 10^5, your solution needs to run in O(n log n) or better to avoid timing out. Understanding time complexity helps you:

Write more efficient code: You can identify bottlenecks and optimize them.
Handle edge cases better: Knowing that your solution scales well with large inputs.
Communicate effectively in interviews: You can explain why one approach is better than another using time complexity.

Practice Problems
Here are a few LeetCode problems where understanding time complexity is essential:
1.Two Sum (Easy) – Optimized with a hash map for O(n) time complexity.
2.Longest Substring Without Repeating Characters (Medium) – Solved efficiently with O(n) using sliding window technique.
3.Merge Intervals (Medium) – Requires sorting, which runs in O(n log n).
4.Largest Rectangle in Histogram (Hard) – An O(n) stack-based approach solves this problem efficiently.

Conclusion
Time complexity is one of the most important concepts to grasp when tackling coding problems, particularly in an interview setting. As you solve more problems on LeetCode, keep analyzing the time complexity of your solutions and look for ways to optimize them. A deep understanding of this will help you write code that performs well even with large inputs.