Time Complexity

Time complexity is the cornerstone of all algorithms, and the reason why we even have different algorithms in the first place. It's very very important to understand time complexity before learning any algorithms.

In very simple terms, time complexity is the method to measure performance of the algorithm. We usually measure runtime of the algorithm as a function of the size of its input. For example, if we perform a sorting algorithm on the array of size N, and we do 3N² + 18N + 1235 operations, we say that algorithm runs in O(N^2) time.

Note that we care only about the highest power of the polynomial (if the time complexity is polynomial), and don't care about constants. For example, both algorithms doing 3N² + 18N + 1235 and (1/2)N² operations are said to have O(N^2) time complexity.

Number of operations performed is a good metric to be looking at because it only depends on the algorithm itself, rather than the computer on which the algorithm is run. The same algorithm doing 10⁸ operations can run in 0.1 second or 2 seconds depending on the machine. For the purpose of the interview questions, it's safe to assume that typical machine (for example, Leetcode server), does about 10⁸ operations per second.

Resources

Before you dive into algorithms, you should read the following materials on the time complexity to really understand it:

• Competitive Programmer’s Handbook – has a nice introductory chapter on time complexity.
• To properly learn time complexity, you should read a chapter in Introduction to Algorithms by Cormen, et al. It's a harder read, but it's a great material to thoroughly understand the topic.
• There are a ton of other great materials on Wikipedia, YouTube and other online resources. Just google "time complexity" and pick what you like.

Quiz

Here is a short quiz to make sure you understand time complexity well. Look at the following code snippets and try to figure out what their time complexity is.

#1

for (int i = 0; i < N; i++) {
    System.out.println("Hi");
}

#2

for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
        System.out.println("Hi");
    }
}

#3

int[] a = {...};
int N = a.length;

int p = 0;
for (int i = 0; i < N; i++) {
    while (i - p > 5) {
        p++;
        a[i] += a[p];
    }
}

#4

int N = ...;
boolean isPrime = true;

for (int i = 2; i * i <= N; i++) {
    if (N % i == 0) {
        isPrime = false;
    }
}

#5

int go(int[] a, int l, int r) {
    if (l == r)
        return a[l];

    int mid = (l + r) / 2;
    return go(a, l, mid) + go(a, mid + 1, r);
}

int[] a = {...};
int N = a.length;

int sum = go(a, 0, N - 1);

#6

private static int go(int[] a, int l, int r) {
    if (l == r)
        return a[l];
    
    int mid = (l + r) / 2;
    int sum = go(a, l, mid) + go(a, mid + 1, r);

    for (int i = l; i <= r; i++)
        sum += a[i];
    
    return sum;
}

int[] a = {5, 7, 9};
int N = a.length;

int result = go(a, 0, N - 1);

#7

String s = "";
        
for (int i = 1; i <= N; i++)
    s = s + "x";

System.out.println(s);

#8

for (int i = 1; i <= N; i++) {
    for (int j = i; j <= N; j += i) {
        System.out.println("Hi");
    }
}