Time Complexity Analysis in Non-Recursive Algorithms
Dive into the essential concepts of time complexity analysis, including true/false statements about algorithm efficiency, analyzing complexity, types of analyses (worst case, best case, average case), and a general plan for evaluating the efficiency of non-recursive algorithms. Explore examples like determining repeated elements in an array and grasp the significance of best, worst, and average cases in algorithm analysis.
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
CS 3343: Analysis of Algorithms Analyzing non-recursive algorithms 4/13/2025 1
True or false? T (also ) F ( ) T (also o) 1. 2n2 + 1 = O(n2) 2. Sqrt(n) = O(log n) 3. log n = O(sqrt(n)) 4. n2(1 + sqrt(n)) = O(n2 log n) 5. 3n2 + sqrt(n) = O(n2) 6. sqrt(n) log n = O(n) F ( ) T (also ) T (also o) 4/13/2025 2
True or false? T (also ) F ( ) T (also o) 1. 2n2 + 1 = O(n2) 2. Sqrt(n) = O(log n) 3. log n = O(sqrt(n)) 4. n2(1 + sqrt(n)) = O(n2 log n) 5. 3n2 + sqrt(n) = O(n2) 6. sqrt(n) log n = O(n) F ( ) T (also ) T (also o) 4/13/2025 3
Analyzing the complexity of an algorithm 4/13/2025 4
Kinds of analyses Worst case Provides an upper bound on running time Best case not very useful, can always cheat Average case Provides the expected running time Very useful, but treat with care: what is average ? 4/13/2025 5
General plan for analyzing time efficiency of a non-recursive algorithm Decide parameter (input size) Identify most executed line (basic operation) worst-case = average-case? T(n) = i ti T(n) = (f(n)) 4/13/2025 6
Example repeatedElement (A, n) // determines whether all elements in a given // array are distinct for i = 1 to n-1 { for j = i+1 to n { if (A[i] == A[j]) return true; } } return false; 4/13/2025 7
Example repeatedElement (A, n) // determines whether all elements in a given // array are distinct for i = 1 to n-1 { for j = i+1 to n { if (A[i] == A[j]) return true; } } return false; 4/13/2025 8
Best case? Worst-case? Average case? 4/13/2025 9
Best case A[1] = A[2] T(n) = (1) Worst-case No repeated elements T(n) = (n-1) + (n-2) + + 1 = n (n-1) / 2 = (n2) Average case? What do you mean by average ? Need more assumptions about data distribution. How many possible repeats are in the data? Average-case analysis often involves probability. 4/13/2025 10
Find the order of growth for sums T(n) = i=1..n i = (n2) T(n) = i=1..n log (i) = ? T(n) = i=1..n n / 2i = ? T(n) = i=1..n 2i = ? How to find out the actual order of growth? Math Textbook Appendix A.1 (page 1058-60) 4/13/2025 11
Arithmetic series An arithmetic series is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. e.g.: 1, 2, 3, 4, 5 or 10, 12, 14, 16, 18, 20 In general: d a a i i ) 1 ( 1 + = Or: = + Recursive definition 1 a a i d Closed form, or explicit formula i 4/13/2025 12
Sum of arithmetic series If a1, a2, , an is an arithmetic series, then + n ( ) n a a = = 1 a n i 2 1 i e.g. 1 + 3 + 5 + 7 + + 99 = ? (series definition: ai = 2i-1) This is i = 1 to 50 (ai) = 50 * (1 + 99) / 2 = 2500 4/13/2025 13
Geometric series A geometric series is a sequence of numbers such that the ratio between any two successive members of the sequence is a constant. e.g.: 1, 2, 4, 8, 16, 32 or 10, 20, 40, 80, 160 or 1, , , 1/8, 1/16 In general: = a ra Recursive definition 1 i i = i a r a Closed form, or explicit formula Or: 0 i 4/13/2025 14
Sum of geometric series + + n if r < 1 if r > 1 if r = 1 1 n 1 ( ) /( 1 r ) r r n = i = n 1 i ( ) 1 /( ) 1 r r 0 + 1 n = i = i 2 ? 0 n 1 = i = lim ? n i 2 0 n 1 = i = lim ? n i 2 1 4/13/2025 15
Sum of geometric series + + n if r < 1 if r > 1 if r = 1 1 n 1 ( ) /( 1 r ) r r n = i = n 1 i ( ) 1 /( ) 1 r r 0 + 1 + 1 n n 2 1 = i + + = = 2 ( 1 1 i n n n 2 2 1 2 ) 2 1 0 n n 1 1 = i = i = = = i lim lim ( ) 2 1 2 n n i 2 1 1 0 0 2 n n 1 ( ) ( ) = i = i 0 i = = = lim lim 2 1 1 1 1 2 2 n n i 2 1 0 4/13/2025 16
Important formulas 3 n n = 2 3 ( ) i n 3 n 1 i n i = 1 ( ) n n + 1 k n = + 1 k k ( ) i n = 1 + 1 k 1 i + n ( ) 1 n n i = 2 ( ) i n n = + = 2 ) 1 + 1 i n n 2 ( 2 ( 2 ) i n n 2 = 1 1 i + ) 1 ( r ( ) 1 r 1 1 n n 1 r i n 1 i = i r = (lg ) n n ( ) ( ) 1 r r = 0 1 i n = lg ( lg ) i n n 1 i 4/13/2025 17
Sum manipulation rules a + = + ( ) a b ii a ii b i i i n = ca c i ii i x n = i = i = x = + a a a 1 i i i + m m i Example: n = i + = i 4 ( 2 ) ? i 1 n n = i = ? i 2 1 4/13/2025 18
Sum manipulation rules a + = + ( ) a b ii a ii b i i i n = ca c i ii i x n = i = i = x = + a a a 1 i i i + m m i Example: n n n = i = i 1 + + = + = + + 1 i i n 4 ( 2 ) 4 2 2 ( ) 1 2 2 i i n n = 1 1 i n n 1 n 2 = i = i = n n i i 2 1 1 4/13/2025 19
i=1..n n / 2i = n * i=1..n ()i = ? using the formula for geometric series: i=0..n ( )i = 1 + + + ( )n = 2 Application: algorithm for allocating dynamic memories 4/13/2025 20
i=1..nlog (i) = log 1 + log 2 + + log n = log 1 x 2 x 3 x x n = log n! = (n log n) Application: algorithm for selection sort using priority queue 4/13/2025 21
Recursive definition of sum of series T (n) = i=0..n i is equivalent to: T(n) = T(n-1) + n T(0) = 0 T(n) = i=0..n ai is equivalent to: T(n) = T(n-1) + an T(0) = 1 Recurrence Boundary condition Recursive definition is often intuitive and easy to obtain. It is very useful in analyzing recursive algorithms, and some non-recursive algorithms too. 4/13/2025 22
Recursive definition of sum of series How to solve such recurrence or more generally, recurrence in the form of: T(n) = aT(n-b) + f(n) or T(n) = aT(n/b) + f(n) 4/13/2025 23
