Notation – The Best, the worst and the Average!

Reading the index of the 1200 page beauty that is CLRS, I realized going in that completing all of it in a given period is not a practical goal. I read the preface first, to see how the authors want us to proceed. Reading it, I realized that I need some basic Algorithmic knowledge beforehand. I needed to learn about the Algorithm Analysis and the different Notations we use.

Why Algorithm Analysis?

Let’s talk about the Sorting problem. There are multiple ways to solve it. There’s Quick-sort, insertion sort, bubble sort, merge sort. Why do we need more than one methods to get the exact same end result?

The Answer to this lies behind the use of these sorting techniques. While all our sorting techniques to the same thing, when we use bubble-sort on an array of 1000 numbers, we discover how much extra time it takes, as compared to quick sort. This is but a small example, in case we have an even bigger set of data, the sorting time will increase exponentially, which will lead to not only an unpleasant User Experience (users hate lag!) but also increase the capacity of our program.

How to compare Algorithms?

Let’s first think of a couple different ways to compare algorithms,

  1. Execution Time: Not a good measure since the execution time would vary not only with the input, but also different computers.
  2. Number of statements executed: This is also an inefficient method, less number of statements do not necessarily mean faster algorithm. The same algorithm implemented in python might be smaller than in C. This does not mean that it is faster.
  3. Amount of time taken to design: While it may be considered for a moment that a well thought out algorithm should perform better, there is no guarantee that an algorithm designed quickly can not be effective or faster.

Time and Space

The ideal solution lies with the comparison of Time and Space of an algorithm. Let us express the running time of a given algorithm as a function of the input size, say n, i.e, f(n). Then we can define the algorithm’s efficiency by how much the time and space requirements grow with the increase in input size.

Order of Growth

This is is how much time of execution depends on the length of the input. Order of growth helps us to compute the running time with ease. We will ignore the lower terms, as these are relatively insignificant for large input. We use different notations to describe the behavior of an algorithm.

O-Notation

To denote asymptotic upper bound, we use the O-notation (Pronounced Big-Oh Notation). This generally denotes the worst case of an algorithm.

For a given function, g(n) we define f(n) = O(g(n))

This means, that at larger values of n, the upper bound of f(n) is g(n). For example, if

f(n) = n4 + 100n2 + 10n + 50, then,

n4 is g(n).

That means, that g(n) gives the maximum rate of growth for f(n) at larger values of n.

Ω-Notation

To denote asymptotic lower bound, we use the Ω-Notation. This generally denotes the best case of an algorithm.

For a given function, g(n) we define f(n) as Ω(g(n)),

Ω(g(n)) = {f(n) : there exists positive constants, c and n0, such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.

This g(n) is an asymptotic tight lower bound for f(n). The objective is to give the largest rate of growth, g(n) which is less than or equal to the given algorithm’s rate of growth f(n).

Θ-Notation

This Notation decides whether the upper and lower bounds of a given algorithm are the same. The average running time of an algorithm is always between lower bound and the upper bound. If the upper bound (O) and lower bound (Ω) give the same result, then the Θ notation will also have the same rate of growth.

So this was the basics of Algorithmic Complexity Analysis! We’ll dive in deeper in upcoming posts.

About Author:

One thought on “Notation – The Best, the worst and the Average!

Leave a Comment

Your email address will not be published. Required fields are marked *