In this chapter we shall learn about below topics:

### 5.1 Definition of Big O notation.

5.2 So why do we try to reduce our function “f(n)” to “g(n)”?

5.3 Example 1.

5.4 Example 2.

5.5 Big O graph

5.6 Commonly used Big O notations

Big O notation is generally used to calculate the complexity of an algorithm, because we want to know on how the algorithm will perform when the input size is increased.

In this chapter we shall know about Big O notation in detail.

## 5.1 Definition of Big O notation:

To say a function f(n) is equal to O(g(n)), if there is a constant “C” and “n0” such that the function f(n) will always be less that “c * g(n)”, can be written as “f(n) < c*g(n)”.

**So what does the above definition mean?**

It means that the function f(n) will not go above the function g(n) for a large value of n. Hence we can consider the function “g(n)” as upper bound for the function f(n).

## 5.2 So why do we try to reduce our function “f(n)” to “g(n)”?

We try to do this because, we know the rate of growth of the function “g(n)” [remember in chapter 3] and hence we try to reduce the function “f(n)” to a known value of rate of growth.

Let us understand the above definition with the help of examples:

### 5.3 Example 1:

f(n) = 6n + 7

g(n) = n

Now we need to check if f(n) is O(g(n)).

i.e we need to check if f(n) = O(n).

So the function 6n + 7 will be equal to g(n), if we can find constants C and n0 such that 6n + 7 <= C*n for all n>= n0.

By analysis we get

When n =5 and C = 8, we can satisfy the condition

6n + 7 <= C * n For all n>= n0

6*5 + 7 <= 8 *5

37 <= 45 for all n >= 5

Hence we can say that the function 6n + 7 is O(n).

Note: There can be many values for C and n0.

### 5.4 Example 2

f(n) = 3n^2 + 4n + 7

g(n) = n^2

We have to prove that the function f(n) is of order O(n^2).

When C= 5 and n0 = 6

We satisfy the condition

3n^2 + 4n + 7 < 5n^2 for all n >= 6;

So like I said in previous topics, we try to reduce the function f(n) to known values of g(n), so that it will easy for us to calculate the running time of the algorithm.

Some of the running time of the function is given below:

1. f(n) = 10 is of order O(1)

2. f(n) = 6n^3 + 2n^2+ 3 is of order O(n^3). Because for larger value of n, (2n^2 + 3) will be negligible.

3. f(n) = 8 log n+ 2n + 5 is of order O(n). This is because the rate of growth of n is greater than log n.

Hence we usually see below graph for O(n).

## 5.5 Big O Graph

## 5.6 Commonly used Big O notations

**O(1)**: Constant time.

**O(long n)**: Logarithmic Time. This type of time complexity can be achieved by continuously dividing a number by a constant.

Example: 16/ 2 = 8 8/ 2 = 4 4/ 2 = 2 2/ 2 = 1

**O(n)**: Linear Time. It can be seen in a single for or while loop.

**O(n* log n)**: Some divide and conquer algorithm have this complexity.

**O(n^2)**: Quadratic Time. This can be achieved by brute force approach. Not very efficient.

Example: Insertion Sort Bubble Sort

**O(2^n)**: Exponential time.

AJ’s guide for DS and Algorithms.Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

## Test

Nice