Big-Oh notation : Theory and Calculation

Invented by: Paul Bachmann and Edmund Landau (German Mathematicians). Thus, Big-Oh notation is also known as Bachmann–Landau notation. Big-Oh tells how fast a function grows/declines. It measures the worst case time complexity
i.e, the longest amount of time an algorithm can possibly take to complete. The notation O(n) is the formal way to express the upper bound (growth rate) of an algorithm's running time. The letter O is used because the rate of growth of a function is also called its order.

Let,
$n \rightarrow$ Size of program's input.
$f(n) \rightarrow$ Any real world function. Example: - Running time of a machine.
$g(n) \rightarrow$ Another function that we want to use as an upper-bound. Not a real world function but preferably simple.

$O(g(n)) =$ { $f(n)$ : there exist $c>0$ and $n_{0}$ such that $f(n) \leq c.g(n)$ for all $n> n_{0}$ }
It implies, $O(g(n))$ also written as $O(n)$ is an infinite set of all functions $f(n)$ that satisfy, there exist $+ve$ constants $C$ and $N$ such that : for all $n\geq N$ ,

$f(n) \leq c.g(n)$

$f(n)\in O(g(n))$

choose ' $n$ ' and ' $c$ ' big enough to fit $1^{st}$ function $f(n)$ under $2^{nd}$ function $c.g(n)$ .

Note: $c.g(n)$ picks speed faster than $g(n)$ . i.e., in the following figure $n^{3}$ starts slow then catches up at P and increase faster than $f(n)$ =n.

Fig. 1.1. Time Complexity

Therefore,

$N$ is a point on the x-axis where arbitrary vertical line PN is drawn.
Right hand-side of arbitrary vertical line PN is $f(n) \leq c.g(n)$ i.e., $f(n)\in O(g(n))$ .

Fig. 1.2. Example of Big O notation: f(n) ∈ O(g(n)) as there exists c > 0 (e.g., C = 4.9) and n₀ (e.g., n₀ =N= 4.3) such that f(n) ≤ cg(n) whenever n ≥ n₀.

Let's understand the concept more by solving some questions,

Q. 1.1. if given $f(n) = 3n + 2$ and $g(n)=n$ find $C$ and $N$ ?

Sol. we know the condition, $f(n)\in O(g(n))$

$f(n) \leq c.g(n)$

$3n + 2 \leq c . n$

Therefore, looking at the inequality its obvious that $C$ must be 4. i.e., $C=4$ .

$3n + 2 \leq 4. n$

$n\geq 2$

Thus, at $C=4$ and $n\geq 2$ , $f(n) \leq c.g(n)$ i.e., $f(n)\in O(g(n))$ .

Note: We found that, for $f(n) = 3n + 2$ and $g(n)=n$ , $f(n)\in O(g(n))$ .

$\therefore$ It is true for $g(n) = n, n^{2}, n^{3},....., n^{n}$ . But, always select the tightest bound, and here it is $g(n)=n$

Q.1.2 Prove that 1,000,000 n $\in O(n)$ i.e., million $n \in O(g(n))$ .

Sol. To Prove:

$\therefore 1,000,000n\leq cn$

Choose, C=1,000,000

$\therefore 1,000,000n\leq 1,000,000n$

Therefore, it doesn't matter where we place the arbitrary vertical line PN, as for any N this relationship will work.

Note:

Big-Oh notation doesn't care about (most) constant factors. i.e., ' $C$ ' - depends on the processor speed of the computer, not on the algorithm.
So, ' $C$ ' is not important. Big-Oh doesn't care about $C$ , and it only tells about the efficiency of an Algorithm.

Therefore, it's unnecessary to write $O(4n)\rightarrow$ though it's mathematically good but not important while calculating Big-Oh.

If I say an Algorithm runs in $O(n^{3})$ ,
$\Rightarrow time\in O(n^{3})$
It doesn't mean the Algorithm is slow. Big-Oh is an upper bound only (as $n\rightarrow \infty$ ) .It is not a lower bound. i.e., It can say something is FAST but it can't say something is SLOW.

Note: that $O(log(n))$ is exactly the same as $O(log(n^{c}))$ . The logarithms differ only by a constant factor, and the big O notation ignores that. Similarly, logs with different constant bases are equivalent.

Q.1.3. Prove that $n^{3}+n^{2}+n\in O(n^{3})$ .

Sol. Randomly set C=3, and N=1,
Note: If we have SUM of functions, the one that grows faster dominates as we go further and further RHS of the arbitrary vertical line PN.

$Time Complexity of function [n^{3}] and [n^{2}] .$

Fig. 1.3. Time Complexity of function $n^{3}$ and $n^{2}$ .

$\therefore$ as $n$ gets BIG ( $n\rightarrow \infty$ ), $n^{3}$ is going to be really! really! BIG. Thus, $n^{2}$ and $n$ won't matter anymore as they will be far... far... behind $n^{3}$ .

$\therefore$ Big-Oh is generally used to pick out the dominating term. And, By 'dominating' we mean "fastest growing term".

2. TABLE OF IMPORTANT BIG-OH SETS

Fig. 2.1. Table of important Big-Oh sets

Smallest to largest.

An algorithm with O(n log n) or faster time (above O(nlog n)) is considered to be "efficient".
Algorithm with $n^{7}$ or slower time (below $n^{7}$ ) are considered "useless".
It also depends on how BIG the problem is. For instance, $n^{6}$ for solving Rubik Cube is OK. As it's a very complicated problem. But, $n^{6}$ for processing Database transaction in Google is NOT GOOD.

Fig. 2.2. Simple graph to understand the Big-Oh complexity: The rate of growth of different function

Fig. 2.3. Recap: Table of important Big-Oh sets.

Note:

$O(n^{c})$ and $O(c^{n})$ are significantly different. $O(n^{c})$ grows faster, irrespective of how big the constant $C$ is.
Super-polynomial is functions that grow faster than any power of n.
Sub-exponential are functions that grows slower than an exponential function, $c^{n}$ .
An algorithm can also take time that is both super-polynomial as well as sub-exponential. Ex: the fastest algorithms known for integer factorization.

3. WARNINGS

I. Fallacious Proof : If you are asked to prove $n^{2}\in O(n)$ , DO NOT say that $C$ =n, then $n^{2}\leq n^{2}$ . $\leftarrow$ It's WRONG! It's FALLACIOUS! as $C$ is a constant and it can't be a variable 'n'.

II. Big-Oh notation DOES NOT SAY what the functions are, it only expresses the relationship between two functions. You have to specify what those functions are.

Example: - Number of emails you send to your father w.r.t time is $O(t^{2})$ ,it implies: you are an increasingly good child.

Fact: BINARY SEARCH on an Array:
# Worst-case running time $\in$ O(log n)
# Best-case running time $\in O(1)$ , when you get lucky & the 1st element was the one you were searching for.
# Memory use $\in O(n)$ , stores all the value you are searching for.

$47+18.log(n) - \frac{3}{n} \in$ O(the worst-case running time)

Q.3.1. prove that $e^{3n} \in O(e^{n})$ ?

Sol.
Note: DON'T SAY that it's true because constant factors don't matter. Because by dividing we can prove that it's a fallacious statement! It's wrong!

$e^{3n} = e^{n}. e^{2n}$ , thus its' bigger than $e^{n}$ by a factor of $e^{2n}$

Q.3.2. Prove that $10^{n} \in O(2^{n})$ ?

Sol. Note: DON'T SAY that it's true because constant factors don't matter. Because by dividing we can prove that it's a fallacious statement! It's wrong!

$10^{n} = 2^{n}. 5^{n}$ , thus $10^{n}$ is bigger by a factor of $5^{n}$

III. The Philosophical Idea (Its just FYI - not to be written in the exam): Big-Oh notation doesn't always tell the whole story.

Suppose, we have two different algorithms. Algorithm 1 runs in exactly $f(n)=n.log_{2}(n)$ ms, and Algorithm 2 runs in $u(n)=100n$ ms. Now, Big-Oh notation suggests that you have to select $u(n)=100n$ over f(n), as f(n) dominates u(n) asymptotically and we are to choose the tightest upper bound.
$u(n)\leq O(f(n))$
$100n\leq n.log_{2}(n)$ , ignored c.

from the equation, its obvious that $log_{2}(n)$ > 100, if $n>2^{100}$ , and usually you are not able to fit that many items in a computer.

Therefore, we can say that $log_{2}(n)\leq 50$ , in practice. That's something we must know in practice.

Q.3.3. If analyzing an algorithm, one finds that time it takes to complete a problem of size ' $n$ ' is given by $T(n)=4n^{2}-2^{n}+2$ . Find Big-Oh of this algorithm.

Sol.

Ignoring constants (as it depends on the hardware on which it runs and not on the algorithm).
Ignoring slower growing terms.

Therefore, T(n) grows with an order of $n^{2}$ .
Thus, $T(n)=O(n^{2})$ .

Q.3.4 Prove $log(n) = O(\sqrt{n})$ .

Sol. We want c>0 and $n_{0}$ such that:

$log(n)\leq c\sqrt{n}$ ; for all $n>n_{0}$ .

Any c>0 would work, the only problem is to find $n_{0}$ . Alternatively, any $n_{0}$ >0 would work if we can find the right 'c'. It's easier to solve for c than for $n_{0}$ .

$c\geq \frac{log(n)}{\sqrt{n}}$

Now,

$\frac{\mathrm{d} }{\mathrm{d} n} (\frac{log(n)}{\sqrt{n}}) = \frac{2-log(n)}{2n^{\frac{3}{2}}}$

So, $\frac{log(n)}{\sqrt{n}}$ is increasing for $n\leq e^{2}$ and decreasing for $n\geq e^{2}$
Thus we can take $c=\frac{log(e^{2})}{\sqrt{e^{2}}} = \frac{2}{e}\approx .7357588824$ , which would work for all $n\geq 1$ .

Q.3.5. Is $log(\sqrt{n})=O(log(n))$ ?

Sol. We know,

$log(\sqrt{n})=\frac{1}{2}log(n)$

by looking at the equation we know that c=1/2, and multiplying by a constant does not change the asymptotic behavior (i.e., ignoring constant). Yes,

$log(\sqrt{n})=O(log(n))$ .

4. Determining running time of a piece of code

To obtain the Big-Oh from a piece of code firstly we must realize that we will be creating a math formula to count how many steps of computations can get executed given an input of some size. i.e., It's an expression of how the execution time of a program scales with the input data. That is, as the input gets bigger, how much longer will the program take? Just a little bit? or a lot longer?

The running time depends on the kind of statements used in the code.

I. Statement sequence



statement 1;

statement 2;

.

.

statement n;

Total time = sum of all the times of all the statements.
Total time = time(statement 1)+ time(statement 2)+...+time(statement n)

If all these statements are simple (i.e., involving basic operations) then the time for each statement is constant and the total time is also constant i.e., O(1).

II. Conditional Statements (if-else-if)



if(condition){

//block 1

}

else{

//block 2

}

Here either 'block 1' will execute else 'block 2'. So, the worst-case time will be the slower block. If block 1 takes O(1) and block 2 takes O(N), the if-else-if would be O(N).

III. Loops



for(i=1; i<N; i++){

//statement sequence;

} //end of loop

Here the loop will run N times. Therefore, statement sequence will also run N times. If these statements are simple then total time for these statements will be O(1). So, the total time for the loop is N*O(1) = O(N).

IV. Nested Loops



for(i=1; i<N; i++){

for(j=1; j<M; j++){ 

//statement sequence;

} //end of loop

} //end of loop

Here the outer-loop will run N times. And every time the outer loop runs the inner loop runs M times. So, the statement sequence will run N*M times. If these statements are simple then total time for these statements will be O(1). So, the total time for the loop is N*M*O(1) = O(N*M).

Special case: If M=N, then inner loop also runs N times every time the outer loop runs. So, total time would be $N*N*O(1)= N^{2}*O(1)=O(N^{2})$ .

V. Function



for(robin=1;

robin<N;

robin++){

batmanCalling(

robin); //function 1

}

Here if the function definition has simple statement sequence then it will take O(1) time. And since the function is in the loop which runs N times, the function will also run N time. So, total time = N*O(1) = O(N).

Now let's solve some questions:

Q.4.1. Find the computational complexity of the following code, where the function returns the sum of all the elements of the array:

int sum(int* data, int N) {
    int result = 0;               // 1
    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }
    return result;                // 4
}

Sol. Let's create a formula to find the computational complexity of the function sum which returns the sum of elements of the array. Let,

$f(N)\rightarrow$ be the function to count the number of computational steps.
i.e., the function that calculates the total number of steps.

$N\rightarrow$ Input of the function i.e., the size of the structure to process.

In laconic terms, Number of steps = $f(data.lenght)$ .

Now, let's find the actual definition of the function $f()$ . This is done from the given source code.

Assume that every sentence that doesn't depend on the size of the input data takes a constant ' $K$ ' number computational steps.

Lets' add the individual number of steps of the function. Variable declaration & return statement doesn't depend on the size of the data array.
$\Rightarrow$ lines 1 and 4 takes ' $K$ ' amount of steps each.Therefore,

$f(N) = K+ .... + K$

The body of for loop executes $N$ times, and the statement in the for loop body takes $K$ steps every time it's executed. So, it takes $K$ * $N$ steps.

$f(N)=K+(N*K)+K$

You have to count how many times the body of the for gets executed by looking at the code. We are ignoring the variable initialization, condition and increment parts of the for statement for simplicity.

To get the actual Big-Oh these are the general steps:

Take away all the constants $K$ . It is a.k.a C or O(1) terms.
From $f()$ get the polynomial in its standard form.
Divide the terms of the polynomial and sort them by the rate of growth.
Keep the one that grows bigger when 'n' approaches infinity.

Our f() has two terms: $f(N)=2*K*N^{0} + K*N^{1}$

Taking away all the $K$ constant (O(1) terms), and the redundant part:

$f(N)=1 + N^{1}$

Since, the last term is the one which grows bigger when $n\rightarrow \infty$ , our sum function has the time complexity of O(N).

Q. 4.2. What is the time complexity of following code:

 while(low <= high) 
{
  mid = (low + high) / 2;
  if (target < list[mid])
    high = mid - 1;
  else if (target > list[mid])
    low = mid + 1;
  else break;
}

Sol. This is a search algorithm that breaks an array of numbers into half, to search a particular element i.e., with every iteration it divides the array into half. So, running time complexity is $\propto \frac{N}{2}$ .

It is a type of divide and conquer algorithm. So it is $O(log(n))$ .

Note: O(log n) basically means: time goes up linearly while n goes up exponentially. So,
if it takes 1 second to compute 10 elements,
it will take 2 seconds to compute 100 elements,
3 seconds to compute 1000 elements, and so on...

graph shows that the rise of the curve decelerates as n increases

Fig 4.1 Example: Plotting log(n) on a plain piece of paper, will result in a graph where the rise of the curve decelerates as n increases

It is $O(log(n))$ when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where

Q. 4.3. What is big-oh of following code:

 void quicksort(int list[], int left, int right)
{
  int pivot = partition(list, left, right);
  quicksort(list, left, pivot - 1);
  quicksort(list, pivot + 1, right);
}

Sol. This is a small logic of Quick Sort algorithm. Now in Quick Sort, each time we divide the array into two parts and every time it takes O(N) time to find a pivot element. Hence it's n*log(n) i.e., O(n log n).

Note: In general, doing something with every element in 1D (i.e., one- dimension) is linear, doing something with every element in 2D is quadratic, and dividing the working area in half is logarithmic.

$O(expression)\rightarrow$ is the set of functions that grow slower than or at the same rate as expression.

Book Recommendation:
1. Introduction to Algorithm
2. Data Structure and Algorithm.

Monday 15 May 2017

Big-Oh notation : Theory and Calculation

2. TABLE OF IMPORTANT BIG-OH SETS

3. WARNINGS

Q.3.5. Is $log(\sqrt{n})=O(log(n))$ ?

4. Determining running time of a piece of code

No comments

Category

Popular Posts

Archive

Monday 15 May 2017

Big-Oh notation : Theory and Calculation

2. TABLE OF IMPORTANT BIG-OH SETS

3. WARNINGS

Q.3.5. Is ?

4. Determining running time of a piece of code

No comments

Category

Popular Posts

Archive

Q.3.5. Is $log(\sqrt{n})=O(log(n))$ ?