Let's Explore Time Complexity

Introduction

A code quality measured by both time and space means how fast the code is completing the input-output process and space means how much memory it uses. We have to compromise one to obtain another and as we all know in this 21st century, the speed of the application matters a lot. So that’s why we are discussing time complexity here, not space.

Definition of Time Complexity

Time Complexity is a way to measure how the runtime of an algorithm increases as the size of the input grows. It helps us understand how efficient an algorithm is in terms of time.

Confused?

It’s ok let’s understand it in simple terms.

It is simply how the runtime of the algorithm changes when the number of inputs varies. It is not the time to run the program as that can depend on several factors like the environment of the system and its configuration. So how exactly is the time complexity calculated?

Mathematical equations are the solution to this problem. Let’s see how.

Overview of Different Types of equations to measure the rate of growth

1. Linear equastion: ax+by+c=0

2. Quadratic equation: ax² + bx + c = 0

3. Cubic equation: ax³ + bx² + cx + d = 0

4. Biquadratic Equations: ax⁴ + bx² + c = 0 (Degree = 4, only even powers)

5. Logarithmic equation: a log x +b

6. Exponential equation: a^x=b

7. Polynomial Equations: anxⁿ + a(n-1)xⁿ⁻¹ + ... + a1x + a0 = 0

Notations to Denote Time Complexity

As every person performs differently when different amounts of stress are on it similarly algorithms can also perform differently in different scenarios.

1. Best-case Time Complexity

   -Performance of algorithm for the best and ideal scenario.

   - Notation: Big-Omega(Ω)

2. Average-case Time Complexity

   -The expected/average time over all inputs

   -Notation: Big-Theta(Θ)

3. Worst-case Time Complexity

   -It is the guaranteed performance in the worst situation.

   -Notation: Big-O

We all know we have to prepare for our worst, the same thing applies to software and algorithms as well that’s why generally we see the worst time complexity to analyze and improve.

💡Note Before Starting with the next section:

Even if you're not familiar with C++, there's no need to worry. Time complexity is a universal concept in computer science—it applies across all programming languages. The examples here are written in C++ for demonstration purposes, but you can understand and implement the same logic in any language you prefer, like Python, Java, or JavaScript.
Focus on the underlying idea, not the syntax. Trust the process, and you'll master it.

Types of Time Complexities

Constant Time Complexity (O(1))

Let's suppose a situation where your productivity isn’t affected by the surrounding variations. When the same thing happens for any algorithm then that has constant time complexity.

We can say:

An algorithm has constant time complexity if its execution time does not depend on the size of the input*. No matter how large the input is, it takes the* same amount of time to complete. It represented by O(1)

Let’s understand through example:

#include <iostream>
using namespace std;

int main() {
    // An array with 4 elements
    int arr[] = {10, 20, 30, 40};  

    cout << arr[2];  //O(1) operation, why? Lets know further in the blog

    return 0;
}

// Output: 30

In the program, we are accessing the 3rd element directly using its index (index starts from 0). This is an O(1) operation as it takes constant time no matter the size of the array.

Logarithmic Time Complexity (O(log n))

Imagine you’ve moved to a new country and you’re trying to find your old friend’s house. You’ve just got the address, but it’s been years since you last visited. How would you go about finding their house?

• Would you search the entire country?

• Would you check every single street in the city?

• How would you narrow it down?

Here's How I Might Do It...

• Step 1: First, I’d look for the country where my friend lives.

• Step 2: Then, I’d narrow it down to the city.

• Step 3: I’d search for the society or neighborhood.

• Step 4: Next, I’d focus on the road and eventually the house number.

In this situation, at each step, the search area shrinks — you don’t need to check the entire world, city, or even the whole neighborhood. With each piece of information, your search space gets smaller and smaller.

Let’s think the same in the algorithm/programming sense. We can say:

An algorithm has logarithmic time complexity, written as O(log n), when the number of operations increases logarithmically with the input size.
This means the algorithm reduces the problem size with each step, typically by half.

Let’s understand through example:

#include <iostream>
using namespace std;

// Function to repeatedly divide the number by 2 and print each step
void divideByTwo(int n) {
    while (n > 1) {
        cout << n << " ";  // Print the current value of n
        n = n / 2;  // Divide n by 2 in each step
    }
    cout << endl;  // To end the output with a new line
}

int main() {
    int n = 32;  // Example input, can be changed to any number
    divideByTwo(n);  // Call the function with n as argument

    return 0;
}

Here, you can see each time the while loop iterations become half. Each time, n is divided by 2, so the values go like this:

$$n,\ \frac{n}{2},\ \frac{n}{4},\ \frac{n}{6},\ \dots... >1$$

We need to find out how many times we can divide n by 2 till its value reaches (≤ 1)

We can write the above expression as:

$$\frac{n}{2^0},\ \frac{n}{2^1},\ \frac{n}{2^2},\ \frac{n}{2^3},\ \dots...,\ \frac{n}{2^k}​$$

So, now we aim to find the value of k.

$$\frac{n}{2^k}​≤1$$

$$n≤2 k ⇒log 2 ​ (n)≤k$$

So, the number of iterations k ≈ log₂(n)

Note: When we find Time complexity we ignore any kind of constants

Linear Time Complexity (O(n))

Imagine you lent your pen to a classmate, but now you're not sure who has it. You can't just shout and ask everyone at once — instead, you have to go to each classmate one by one and ask, "Do you have my pen?"

This process of going through each classmate individually is called iteration in programming — just like checking every item in a list one at a time to find what you need.

Let’s think the same in the algorithm/programming sense. We can say:

An algorithm has linear time complexity, written as O(n), when the number of operations increases directly in proportion to the input size

You go through each element one by one — no skipping, no halving, just a straight pass.

Let’s understand through example:

#include <iostream>
using namespace std;

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";  // One operation per element
    }
    cout << endl;
}

int main() {
    int arr[] = {5, 10, 15, 20, 25};
    int n = sizeof(arr) / sizeof(arr[0]);

    printArray(arr, n);  // O(n) function

    return 0;
}

Here we have to print each element. We have to go to each element and iterate that. That means if the size of the array increases the iteration time also increases. Hmm…

You are thinking right. Time increases linearly with the input size. This means if the program takes 1s to print one element then for a 100-size array it takes 100, for 200 elements takes 200s, and so on.

Quadratic Time Complexity (O**(n²)**)

Let’s say you’re organizing a classroom activity where every student has to shake hands with every other student once.
If there are n students, each student goes around and interacts with (n - 1) others.

So, total interactions ≈ n × n = n² (ignoring minor adjustments like not shaking hands with themselves).

This is called Quadratic Time Complexity – O(n²).

It often happens when:

• You use nested loops, like a loop inside another loop.

• You compare every pair of items (e.g., in bubble sort, selection sort, etc.)

Let’s check an example:

#include <iostream>
using namespace std;

void printAllPairs(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << "(" << arr[i] << ", " << arr[j] << ")\n";
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr);
    printAllPairs(arr, n); // O(n²) Time Complexity
    return 0;
}

In this algorithm each time the outer loop runs once, the inner loop runs n times — leading to n × n = n² operations. So that’s why the time complexity of the algorithm will be O(n²)

Cubic Time Complexity (O(n³))

Till now you people become smart enough to understand time complexity so let’s directly understand Cubic Time Complexity with an example.

 #include <iostream>
using namespace std;

void printTriplets(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                cout << "(" << arr[i] << ", " << arr[j] << ", " << arr[k] << ")\n";
            }
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printTriplets(arr, n); // O(n³) function call

    return 0;
}

Let’s examine this example:

• here i loops go from 0 to n-1

• For each i, j loops go from 0 to n-1

• For each j, k loops go from 0 to n-1

• Total iterations: n × n × n = n³

So time complexity of the code will be O(n³)

Exponential Time Complexity (O(2ⁿ))

Exponential time algorithms double the number of operations with each added input — making them grow very fast.
These commonly appear in:

• Recursive algorithms with two or more branching calls

• Problems like Fibonacci, subset generation, combinatorics, and backtracking

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 5;
    cout << "Fibonacci of " << n << " is: " << fibonacci(n) << endl;
    return 0;
}

Let’s examine this code:

• Each call to fibonacci(n) branches into two more calls: fibonacci(n - 1) and fibonacci(n - 2)

• This tree of calls doubles in size with each level, forming 2ⁿ total calls in the worst case.

Factorial Time Complexity (O(n!))

In O(n!), the number of operations grows as the factorial of n, which means:

n!=n×(n−1)×(n−2)×⋯×1n! = n × (n - 1) × (n - 2) × \dots × 1n!=n×(n−1)×(n−2)×⋯×1

Don't worry if this looks intimidating — it's just a normal multiplication sequence. For example:

• 2! = 1 × 2 = 2

• 3! = 1 × 2 × 3 = 6

• And so on...

Let’s relate this to real-world scenarios — it’ll make things easier:

• Traveling Problem: Let’s find all possible orders to visit n cities → n! combinations
  (Try to visualize this by listing all routes for 3 or 4 cities!)

• Password Cracking (Brute Force): Trying all order-sensitive combinations → again, n! possibilities

Let’s go back to time complexity.

This kind of time complexity usually shows up in:

• Generating all permutations of a set

• Some other complex algorithms

🔖 Note:
Don’t stress too much!
If you’re able to understand Exponential Time Complexity (O(2ⁿ)), you're already at a solid level.

Exponential and Factorial time complexities are introduced here just to give you a taste of the more complex challenges in computer science — no pressure to master them right away!

Conclusions

1. Time complexity is a way to measure how the runtime of an algorithm changes based on the size of the input.

2. We have 3 notations to donate Time Complexity:

   • Best case time complexity(Ω)

   • Average case time complexity(Θ)

   • Worst-case time complexity(Big-O)

3. Types of Time Complexities: O(1), O(log n), O(n), O(n²), O(n³), O(2ⁿ), O(2ⁿ), O(n!)

🏁 Final Note: Keep Going, You're on the Right Track!

Understanding time complexities is like learning how efficiently your code runs. It might seem overwhelming at first, but remember — small efforts make a big difference, so keep moving forward!

And Yehh….

Next time when someone says an application isn’t running well, think about time complexity. Could it be that the algorithm isn't optimized for the input size? This understanding will help you identify bottlenecks and improve performance.