Examples and Analysis of Algorithm Complexity
Explore various examples and analysis of algorithm complexity, including procedures, running time analysis, big-Oh notation, and more. Understand the time complexity of linear search, loop iterations, and code execution prediction. Dive into examples showcasing O(n) and O(n^2) complexities.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Complexity Examples procedure max_diff(a1, a2, , an: integers) min := a1 max := a1 for i := 2 to n if ai< min then min := ai else if ai> max then max := ai m := max - min Comparisons: Time complexity is O(n).
Analyzing Running Time int sum = 0; int i = 0; for(i=2; i < n; i++) { cin>>x; sum = sum + x; } avg = sum / n The computing time for this algorithm in terms on input size n is: T(n) = 4n + 5 = O(n). Statement 1 2 3 4 5 6 7 8 Number of times executed 1 1 1 n+1 n n n 1
Example Compute the big-Oh running time of the following C++ code segment: for (i = 2; i <= n; i++) { sum += i; } The number of iterations of a for loop is equal to the top index of the loop - the bottom index + one more instruction to account for the final conditional test. (if i<n) Note: if the for loop terminating condition is i <= n, rather than i < n, then the number of times the conditional test is performed is: ((top_index bottom_index) + 2) In this case, we have n - 2 + 2 = n compares. The assignment in the loop is executed 2(n-1) times. So, we have (1+ n + n-1 + 2n-2)= (4n+2) = O(n).
Example examine a piece of code and predict the number of instructions to be executed Inst # Code for (int i=0; i< n ; i++) 1 { cout << i; 2 p = p + i; 3 }
Another example F.C. F.C. Inst # Code n+1 n+1 for (int i=0; i< n ; i++) 1 n(n+1 ) n2+n for int j=0 ; j < n; j++) 2 n2 n*n 3 { cout << i; n2 n*n 4 p = p + i; ____ } 3n2+2n+1 discarding constant terms produces : 3n2+2n Big O = O(n2) clearing coefficients : n2+n picking the most significant term: n2
Example Suppose f(n) = n2 + 3n - 1. We want to show that f(n) = O(n2). f(n) = n2 + 3n - 1 g(n) = n2
Example f(n) = 2n7 - 6n5 + 10n2 5 = O(n7)
Complexity of Algorithms Describe the (worst-case) time complexity of the linear search algorithm. , an ) i=1; while ( i <= n and x !=ai ) { i := i+1 } if i <= n, then location := i else location := 0 The time complexity depends on the number of comparisons because they are the basic operations used. Procedure linear search (x: integer a1, a2, . . . So how many comparisons are there if (in the worst-case) you have to go to the end of the list?
Complexity of Algorithms At each step of the loop, there are two comparisons. Outside the loop, there is one more comparison. 1. 2. Therefore, if the list has n elements, we will have 2 n + 1 comparisons. Total = 1+2n+1 + 1= 2n+3 The complexity (in this case) is denote as O(n)
