Time Complexity
Nakib Hayat Chowdhury
Assistant Professor, Dept. of CSE, BAUST
1
Every extraordinary feet began in ordinary circumstances. I will start my journey of success from where I am now.
License
Your are free –
• to Share – to copy, distribute and transmit the work
• to Remix – to adapt the work
For non commercial and educational purpose.
2
Linear Time
How to find the biggest number from a list of N numbers
A1 A2 A3 ………………. AN
• MAX = A1
• i=1 //2
• WHILE (i <= N)
• IF (Ai > MAX)
• MAX = Ai
• i=i+1
• PRINT MAX
• STOP
3
Different Search Technique
Elements : 11 13 33 45 56 64 73
1. Linear Search
2. Binary Search
4
Different Cases
1. Worst Case
2. Best Case
3. Average Case
5
Time Complexity of Binary Search
Elements : 11 13 33 45 56 64 73
•N
• N/2
N / 2k = 1
• N/4 Þ N = 2k
. Þ 2k = N
.
Þ log2 2k = log2N
.
Þ k = log2N
• Until the list size is 1
6
Complexity
1. Linear Complexity
2. Logarithm Complexity
3. N2 or N3 Complexity
4. 2N Complexity
7
Quadratic Time Complexity (N2)
Make a pair on this element
• i=1
• WHILE (i <= N)
• j=1
• WHILE (j <= N)
• PRINT Ai Aj
• j++
• i++
• STOP
8
Time Complexity : Where is Time?
• It does not count the time!
• It count the number of steps!!!
9
Big O Notation
N2+2N+1 = O(N2)
10
Big O Example
Because it has to calculate constant operation.
O (1)
Not depends on any variable.
11
Big O Example
Though it will stop after 1000 loop if n is greater than 1000
O (n)
But we have to consider the worst case
12
Big O Example
• The outer loop will run for n time and for
every time-
• The inner loop will run for n for 1st time, (n-1)
for second time and so on.
• So time complexity : n + (n-1) + (n-2) + ….. =
= (n2 + n) / 2
• Here n2 and (n2+n) => n2
• Again n2 / 2 => n2
O (n2)
13
Big O Example
Because the complexity of recursive function depends on the depth
O (n)
of that function.
14
Big O Example
15
Big O Example
16
Big Omega Notation
N2+5n = (N2)
17
