Scribd
Upload
7 views

Slide 7 - Time Complexity

Uploaded by

crid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
7 views

Slide 7 - Time Complexity

Uploaded by

crid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 17

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

You might also like