unit 1 SIXTH.pptx Algorithm Complexity Time

Algorithm & Algorithm Complexity - Time

1. SANJIVANI K. B. P. POLYTECHNIC, KOPARGAON With NBA ACCREDIATED programs , Approved by AICTE, New Delhi, Recognized by Govt. of Maharashtra , Affiliated to Maharashtra State Board of Technical Education, Mumbai, ISO 9001:2015 Certified Institute Department:- Computer Technology Class:- CM3I Name of Subject:- Data Structures Using 'C‘ MSBTE Subject Code:- 22317 Name of Faculty: Prof. Vaibhav A. Parjane 1

2. Topic to be Covered Time Complexity 2 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

3. Time Complexity : Time complexity is the total time taken by the algorithm to perform the intended task. It is also known as frequency count. Eg : consider the FOR LOOP For ( i =0 ; i <n ; i ++ ) Atleast once (1) + (n+1) + n = 1 + (n+1) +n = 2n + 2 true false 3 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

4. Time Complexity: Ex: Consider the following algorithm to add two numbers   Here, algorithm has only two simple statements so the complexity of this algorithm is 2 4 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

5. Example void main ( ) { int i , n , sum , x; sum = 0; printf (“Enter number of elements : ”); scanf (“ %d” , &n); for (i=0 ; i<n ; i++) { scanf (“ %d” , &x); sum= sum + x; } printf (“sum = % d” , sum ); } In the for loop, the condition (i<n) will be executed (n+1) times , and not ‘n’ times. For all values of ‘i’ between 1 and n , the condition (i<n) will evaluate to true and when ‘i’ becomes (n+1) , the condition (i<n) will evaluate to false. Thus the above instruction will be executed (n+1) times. 5 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

6. Calculation of computation time Statement Frequency sum = 0 1 printf (“Enter number of elements : ”); 1 scanf (“ %d” , &n); 1 for ( i =0 1 i <n n + 1 i ++ n scanf (“ %d” , &x); n sum= sum + x; n printf (“sum = % d” , sum ); 1 =1 + 1 + 1 +1 + (n+1) + n + n + n + 1 =(6+4n) 6 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane

7. Example : i =1; while ( i < = n) { x = x +1 ; i = i + 1; } Statement Frequency i =1; 1 while ( i < = n) n +1 x = x +1 ; n i = i + 1; n =1 + (n+1) + n + n =(2+3n) 7 Sanjivani K. B. P. Polytechnic, Kopargaon Department of Computer Technology Prof. Vaibhav A. Parjane