Complexity

Two programs can both solve the same problem and produce the same correct answer — yet one can be a million times faster than the other. How do you know which one is better? How do you even measure it?

That is exactly what this lesson answers. Complexity is the scoreboard for code. It tells you — before you even run the program — how it will behave when the data gets big. This is what every interviewer means when they ask "what is the time complexity of your solution?"

What is Time Complexity?

Time complexity does not measure how many seconds your code takes to run. If it did, a slow computer would make every program look bad, and a fast computer would make every program look good. That is not useful.

Instead, time complexity measures how the number of steps grows as the input size grows. It is about the relationship between input and effort — not the actual clock time.

What is Space Complexity?

While time complexity is about speed, space complexity is about memory. It measures how much extra memory your program uses as the input size grows.

In code, this means: does your program create extra variables, arrays, or data structures that grow with the input? Or does it work with a fixed small amount of memory no matter how large the input is?

Big O Notation — The Universal Language

Big O notation is how engineers all over the world describe complexity in a standard way. When someone says "this algorithm is O(n²)" — every engineer on earth knows exactly what that means.

The letter n always represents the size of the input. If you have an array of 100 elements, n = 100. If you have 1 million users, n = 1,000,000. Big O describes what happens to the number of steps as n grows.

Best, Average, and Worst Case

The same algorithm can behave very differently depending on what data you give it. This is why we talk about three cases.

How to Analyse Any Code — Step by Step

Now let us actually apply all of this. Here is the method — four simple rules you can apply to any piece of code to figure out its Big O complexity.

Example 1 — O(1) Constant Time

No matter what value n has, this function always does exactly the same number of steps.

int getFirstElement(int arr[], int n) {
    return arr[0];  /* always 1 step — doesn't matter if n is 10 or 10 million */
}

Example 2 — O(n) Linear Time

The loop runs once for every element. More elements = more steps, directly.

void printAll(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {   /* this loop runs n times */
        printf("%d\n", arr[i]);  /* one step each time */
    }
    /* total steps = n → O(n) */
}

Example 3 — O(n²) Quadratic Time

A loop inside a loop. The inner loop runs n times for every iteration of the outer loop. Total steps = n × n.

void printPairs(int arr[], int n) {
    int i, j;
    for (i = 0; i < n; i++) {        /* outer loop — runs n times */
        for (j = 0; j < n; j++) {    /* inner loop — runs n times for EACH outer step */
            printf("(%d, %d)\n", arr[i], arr[j]);
        }
    }
    /* total steps = n × n = n² → O(n²) */
}

Example 4 — Mixed: What is the complexity here?

When you have multiple parts, identify the dominant one.

void mixedExample(int arr[], int n) {
    int x = arr[0];          /* O(1) — single statement */
 
    int i;
    for (i = 0; i < n; i++) {     /* O(n) — single loop */
        printf("%d\n", arr[i]);
    }
 
    int j, k;
    for (j = 0; j < n; j++) {     /* O(n²) — nested loops */
        for (k = 0; k < n; k++) {
            printf("%d %d\n", arr[j], arr[k]);
        }
    }
    /* Total = O(1) + O(n) + O(n²) */
    /* We keep only the dominant term → O(n²) */
}

What These Numbers Actually Mean

Let us make this real. Here is how many operations each complexity class produces for different input sizes. Assume your computer does 1 billion operations per second.

You Are Ready for Lesson 3

You now have the single most important mental tool in all of DSA — the ability to look at any piece of code and judge whether it is efficient or not. Every lesson from here uses this language. When we say "arrays give O(1) access" or "bubble sort is O(n²)", you now know exactly what that means.

In Lesson 3 we dive into Arrays — the very first and most fundamental data structure. We will build them from scratch in C, understand exactly how they sit in memory, and write the core operations: insert, delete, search, and traverse.