**is the most efficient tool to compare the efficiency of algorithms. it represents the upper bound of an algorithm. it tells the asymptotic behavior of a function and how fast a function f(n) grows as input size n becomes large.**

__Big O notation in data structures__##
__Big O notation - Definition__

A function f(n) is order of g(n) if there exists constants c and n_{0}such that function f(n) <= c*g(n) where the n is greater then n0.

__here the g(n) is the upper bound of function f(n)__

**Note:**__let's understand it with an example__

let's say we have a function f(n) = 5n + 4 then how we calculate the order of the function f(n).

f(n) = 5n + 4

the upper bound of function f(n) is n.

so g(n) = n

let's find the constants c and n

_{0}

_{}using the definition we can write the function f(n) like this.

f(n) <= c*g(n)

5n + 4 <= c*n for all n >= n

_{0}

_{}let's take c = 6 and n

_{0}= 4 then equation is

5n + 4 <= 6n for all n >= 4

so the function f(n) = 5n + 4 is order of n. and in mathematical term.

**5n+4 is O(n)**

__let's take another example__

f(n) = 3n

^{2 }+ 4n + 7

so, g(n) = n

^{2}

for values c = 5 and n

_{0}= 6 function f(n) is

3n2 + 4n + 7 <= 5n

^{2}for all n >= 6

so the function f(n) = 3n

^{2}+ 4n + 7 is order of n

^{2}

3n2 + 4n + 7 is O(n

^{2})

###
__Method to find the Big O notation of function__

to find the Big O notation of a function we have some rules.####
__Rule First:__

Keep the fastest growing term and discard the lower terms and constants.for example, if the function f(n) = 3n

^{2}+ 4n + 2 then the fastest-growing term is only 3n

^{2}. so we will keep only 3n

^{2}and discard the lower terms 4n and constant 2 from the function f(n).

####
__Rule Second:__

Ignore the coefficients from the equation.for example, we have function f(n) = 3n

^{2}then we remove the coefficients 3 from equation 3n

^{2}.

####
__Rule third__

If the function f(n) is constant then we say that f(n) is the order of 1.for example we have function f(n) = 4 then it's an order of 1. because function f(n) is constant.

####
__Rule Fourth__

The base of the logarithm is not important.
log

_{a}n = log_{b}n / log_{b}aboth values for log a and b are constants. and we don't consider constant values so we ignore them.

for example if the function f(n) = 8log2n. then we can say that function f(n) is the order of log n.

__let's take an example to understand how we find the Big O for function.__

__Example 1:__

f(n) = 45

here the function f(n) is constant then it's and order of 1

f(n) is O(n)

__Example 2:__

f(n) = 6n

^{3}+ 27log

_{2}n + 2n

here we apply the rules

__first,__remove the lower terms and constants, then

f(n) = 6n

^{3}

__second,__remove the coefficients, then

f(n) = n

^{3}

so the function f(n) is the order of n3.

f(n) is O(n3)

__Example 3:__

f(n) = log

_{2}n + nlog

_{10}n

f(n) = nlog

_{10}n

so function f(n) is the order of n logn.

f(n) is O(n logn)

###
__Bound of an algorithm__

there are two bounds of the algorithm. one is tight and the other is a loose bound.for a function f(n) there can be many functions g(n) such that f(n) is O(g(n))

let's say we have a function f(n) = 5n

^{2}+ 4n + 8 then the order of function f(n) is n2. but it's also the order of n

^{3}, n

^{4}and n

^{n }

so

the least upper bound of an algorithm is called the tight upper bound and all other bounds are called a loose upper bound.

so the tight upper bound of function f(n) is n

^{2}and all other bounds are loose upper bounds.

__the loose upper bounds are not informative as as the tight upper bound. so we only consider the tight upper bound of an algorithm.__

**Note:**###
__Big O analysis of algorithms __

we can also analyze the big O of an algorithm. so to do this first we need to express the running time of an algorithm as a function of input size n. let's say we have a function T(n) that represents the running time of an algorithm in terms of n. then we need to find the big O of function T(n).

let's say we have 4 algorithms A, B, C, and D. and the function T(n) represents the running time of an algorithm. then to analyze the algorithm that which one is efficient we need to calculate the big O for function T(n) of all 4 algorithms.

so algorithm A is the order of n

^{3}, similarly, algorithms B, C, and D are in order of n

^{2}, n, and n

^{2}. as shown in the above image.

so algorithm C is efficient for our problem because algorithm c has the fastest running time rate.

Also, read other tutorials as well

- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Priority queue
- Polish notation
- Tree in the data structure
- Binary tree
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures

## 0 Comments