Complexity Analysis

We all realize that Computer Science Engineering involves creating computing systems that can solve real-world problems. Dealing with the real world follows that —

1. We have to deal with a huge amount of data.
2. We have to determine ways through which we can deal with this data as efficiently as possible.

To dispense with any vagueness associated with the word efficiency, let’s see how Cambridge defines it:

The quality of achieving the largest amount of useful work using as little energy, fuel, effort, etc. as possible:

If I translate this to our world — the quality of achieving the system’s objective by dealing with the largest possible amount of data using as few resources as possible.

In the DS&A world — resources can further mean two things — time and memory. The algorithms we devise and data structures we implement should be efficient (See the definition and its translation again!).

We must know that our initial intuition is often rather naive (most of the time). If I want to see how much time or space an algorithm consumes during its execution, a simple answer would be — just measure it. And to compare two algorithms or two implementations — just measure the two and see which consumes less. Fine. But it isn’t a really good idea. This is because these executions heavily depend on the underlying hardware, operating system and its nuances, and other variables that computing systems go through. This means we cannot possibly define its efficiency just by its execution time or an average of multiple runs reliably.

Because of these problems, we in computer science speak in abstract terms. We define a function that describes how the resource consumption changes with the size of its input. Particularly when the input size grows, this is because our major worries come from scaling in the real world — when suddenly, the amount of data to deal with shoots up. That is why we are interested in talking in terms of this function. Complexity Analysis is a method in Computer Science that involves determining this function for any algorithm and comparing two or more algorithms or implementations. We in CS Engineering make use of this analysis to choose a more efficient approach to solving a problem.

Because of these two conclusions that we established:

1. Complexity analysis is about the growth of resource consumption with respect to the input size.
2. We are really interested with the bigger input sizes because that is where scalability becomes important in the real world.

Complexity Analysis is done asymptotically. Asymptotic analysis is about studying and comparing the eventual growth of functions. And to express this asymptotic nature mathematically — limits are the obvious tool.

Let’s build this one by one.

The first step that would make sense would be: express the number of steps the algorithm does in terms of the input size. For example:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cout << i << " ";
    }
    return 0;
}

The loop will run print the number n times. This means the whole algorithm can be represented as n .

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        cout << endl;
    }
    cout << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << i << " ";
    }

    return 0;
}

// Output for n = 5
// 5
// 1 2 3 4 5
// 1 2 3 4 5
// 1 2 3 4 5
// 1 2 3 4 5
// 1 2 3 4 5

This can be represented as n² + n .

Now, suppose an expression like: 3n²+10n+7. As we know that we are really interested in the eventual growth of functions, if we define a function like:

f(n) = 3n²+10n+7

and note how the value of f(n) grows for increasing values of n — we would notice that 3n² would dominate the value. This means that eventually 3n² becomes the defining term for this function; or in other words — the dominant term.

Now hold onto this observation a bit more.

Let’s try to compare expression with the dominant n². To do that we will divide them:

As we know we are interested in the eventual growth of the input size, we can make use of limits:

This means that eventually f(n)is approximately 3 times g(n). One more thing to note is that we are interested in the multiplicative factor. Here, it is 3. This means that the multiplicative factor would eventually settle at this constant rate — 3, which is not a problem. A problem comes in cases like this:

Get Shubham Thakur’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

If we had compared it instead with, say, n, the multiplicative factor would be n. Which means that the ratio itself would grow at a rate of n. Which is bad. Apply the limit, and it would become infinite.

Now the question arises — why did we do this comparison? The answer is — this helps us to sort these numerous functions and their expressions into buckets, buckets that have common properties, common graphical representations, common methods to deal with. Imagine dealing with hundreds of algos and all their different expressions of complexity! That would be a lot of work. We abstract further and create buckets. These buckets are growth classes represented by common reference functions — 1, n, logn, n², n³, 2^n. We can say that:

f(n) = 3n²+10n+7

has quadratic growth. And

f(n) = 3n

has linear growth.

But there is a gap here — I say f(n) = 3n²+10n+7 belongs to n², but in what sense? I mean, what is the relationship between the two?
To say explicitly, 3n²+10n+7 has the same asymptotic growth as n². Formally, this is called Theta (Θ) notation, represented as:

f(n)=Θ(g(n))

roughly saying that both f(n) and g(n) belong to the same growth class and would have the same asymptotic growth. By this, we can write
f(n) = 3n²+10n+7 as Θ(n²).

But what if we do not want a growth class that would have the same asymptotic growth but be something like an upper bound? This means asking — ‘What is the worst way this algorithm can perform — an upper bound?’ Here comes Big-Oh notation.

n=O(n²)

This means saying: the function grows no faster than the reference function, up to a constant factor. By this, we can write f(n) = 3n²+10n+7 as O(n²) as well, since it wouldn’t grow faster than this.

But see here: we can write this as well: f(n) = 3n²+10n+7 = O(n³). Why? Again — this wouldn’t grow faster than n³ because (hilariously) it is n². It is just like this joke -

Jack, in his mid-forties — want to ride the merry-go-round. The security stops him.
Jack: But I am at least lighter than you, sir!

Or

Doctor: What is your weight, sir? I need to see if you are not overweight.
Patient: I am less heavy than an elephant.

Well, this doesn’t sound informative (neither does f(n) = 3n²+10n+7 = O(n³)). That is why we do not make these jokes and say: f(n) = 3n²+10n+7 = O(n²) although the joke was technically true. To conclude — Big Oh is not the tightest upper bound.

If you care about a lower bound, it is Big Omega notation.

f(n)=Ω(n²)

This means saying: the function grows faster than the reference function, up to a constant factor. But again, it is not the tightest lower bound as well.

Two other useful notations are little-o and little-omega. Now, as Big-Oh says: the function grows no faster than the reference function, up to a constant factor; if we try to translate it to linear inequalities, it becomes like:

x ≤ y

Don’t tighten it!

x < y. Little-o says — the function grows strictly slower than the reference function, up to a constant factor.

Same goes for little-omega. As Big-Omega says: the function grows faster than the reference function, up to a constant factor; it becomes:

x ≥ y

Now tighten it!

x > y. Little-omega says — the function grows strictly faster than the reference function, up to a constant factor.

All done for today, but I will admit there are a few additional topics I would like to write on. I intend to publish them subsequently as addenda. I will link them once they are up.