Time Complexity in DSA: Big O, O(n) & O(log n)

Factorial Trailing Zeroes Problem

For example, consider the Factorial Trailing Zeroes problem. It is one of the famous LeetCode problems: to identify how many zeros are there in the factorial of a number.

#include 

int main() {

    int n = 10; // input

    unsigned long long fact = 1;

    // 1. Calculate the factorial
    for (int i = 1; i <= n; i++) {
        fact *= i;
    }

    // 2. Count the trailing zeros
    int zeros = 0;
    while (fact % 10 == 0) {
        zeros++;
        fact /= 10;
    }

    printf("Trailing zeros: %d\n", zeros);

    return 0;
}

Here, first we calculate the factorial and then we count the zeros by using the modulo and divide operators.

The question is: how much time does it take to solve this problem?

Finding the factorial of a number takes O(N), and finding how many zeros it has takes O(log₁₀N) time.

We need to analyse the time complexity of this solution.

Two Kinds of Problems

There are two kinds of problems:

• Decidable problem
• Undecidable problem

Decidable Problem

A decidable problem is a problem that requires polynomial time to solve using a deterministic algorithm for finite input.

For example, with N input there are N number of CPU computations to solve the problem:

Undecidable Problem

An undecidable problem is a problem that requires exponential time to solve using a deterministic algorithm for finite input.

For example:

Polynomial functions are tractable problems and can be solved within a finite, practical time, but exponential functions are intractable problems — we cannot solve them within a practical amount of time.

Exponential Function 2^N

To prove that, consider the exponential function 2^N.

Assume we have a hypothetical fastest computer which executes M instructions per second, where 1 M instructions = 2²⁰ bytes, 1 KB = 2¹⁰ bytes, 1 GB = 2³⁰ bytes.

In one year, how many instructions is it able to compute?

Now assume the exponential function 2^N, where N = 200.

To find how much time it takes to compute the exponential function 2^N where N = 200:

Therefore, to compute this algorithm, it takes approximately 2¹⁵⁴ years.

Unfortunately, we are all mortal, which is a shame, because waiting 2¹⁵⁴ years to get the output isn’t exactly practical.

Optimizing Factorial Trailing Zeroes

To solve this problem, we need to analyse the number system.

For example, 5 multiplied with any even number gives a trailing zero:

25 multiplied with any multiple of 4 gives a trailing of 2 zeros:

Now let us analyse the pattern. By counting how many 5’s and powers of 5 are in the factorial of a number, we can easily identify how many trailing zeros are in that factorial.

Finding Trailing Zeroes in 19!

To find how many trailing zeros are in 19!:

Finding Trailing Zeroes in 30!

To find how many trailing zeros are in 30!:

Based on this logic, let us implement the solution in C.

int res = 0, i = 1;

while (n >= 5) {
    n /= 5;
    res += n;
}

printf("%d", res);

The optimized method completely skips calculating the factorial (an exponential operation) and drops the time complexity down to O(log N) — logarithmic time.

We need to think beyond simply solving a problem. By understanding the underlying mathematics, identifying patterns, and analysing time complexity, we can develop more efficient solutions.

What Is Time Complexity?

We now know why time complexity is important, having solved the factorial trailing zeros problem. Now let’s dive deeper into time complexity.

Time Complexity is the estimation of the CPU computation required to complete the execution of an algorithm.

Let us consider the sum of an array of n elements:

int AlgoSum(int *a, int n) {

    // a[0...n] array of n elements
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum = sum + a[i];
    }

    return sum;
}

Frequency Count of Sum of Array

Here we increment the value and check the condition on every iteration, for n total iterations:

Therefore, the condition check is evaluated 2 times for every one of the n iterations.

The sum variable is initialized only once, so its frequency count is 1 (constant).

Inside the loop body, sum = sum + a[i] executes n times.

The total frequency count of the whole program is 3n + 1, but in Asymptotic notation, constant terms and coefficients are neglected. Therefore, O(n) is the time complexity of the entire program.

Time Complexity of Loops

Wherever iteration takes place, time complexity plays a crucial part — not only in loops, but also in recursive functions or goto statements. For a better understanding, let’s consider for loops.

Simple Loops

for (int i = 1; i <= n; i++) {
    printf("IIES");   // prints n times
}

“IIES” will print n times. So the time complexity is O(n).

for (int i = n; i >= 1; i--) {
    printf("IIES");   // prints n times
}

The same thing happens here. “IIES” will print n times. So the time complexity is O(n).

Loop With Multiplication

Let us consider a third example:

for (int i = 1; i <= n; i = i * 2) {
    printf("IIES");
}

In every iteration, the variable i is doubled, creating a series of powers of 2:

This continues up to k times, but at the k+1th time it fails the condition and exits the for loop.

Therefore, the time complexity is O(log₂n).

Verify O(log n) Time Complexity

Let us verify this time complexity.

For example, consider n = 16:

4 times, the loop will execute when the n value is 16.

for (int i = 1; i <= 16; i = i * 2) {
    printf("IIES");
}

Output:

IIES
IIES
IIES
IIES

We have proved why we denote this scenario as O(log n).