Analysis of AlgorithmsCS3381Des&AnalofAlg(2001-2002SemA)CityUnivof HK/DeptofCS/HelenaWong2.AnalysisofAlgorithms-1
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 1 Analysis of Algorithms
Analysis of AlgorithmsComing upAsymptotic performance, Insertion SortA formal introduction to asymptotic notation(Chap 2.1-2.2, Chap 3.1)CS3381Des&AnalofAlg(2001-2002SemA)CityUnivofHK/Deptof CS/HelenaWong2.AnalysisofAlgorithms-2
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 2 Analysis of Algorithms Coming up Asymptotic performance, Insertion Sort A formal introduction to asymptotic notation (Chap 2.1-2.2, Chap 3.1)
Asymptotic performanceIn analysis of algorithms, we care most aboutasymptoticperformance“"How does the algorithm behave as theproblem size gets very large?"Running timeMemorylstorage requirementsBandwidth/powerrequirements/logicgates/etcCS3381Des&AnalofAlg(2001-2002SemA)CityUnivofHK/DeptofCS/HelenaWong2.AnalysisofAlgorithms-3
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 3 Asymptotic performance “How does the algorithm behave as the problem size gets very large?” Running time Memory/storage requirements Bandwidth/power requirements/logic gates/etc. In analysis of algorithms, we care most about asymptotic performance
Asymptotic performanceAssume: an algorithm can solve a problem of size n in f(n)microseconds (10-6 seconds).f(n)n=20n=40n=60Log2n4.32 * 10-6sec5.32* 10-6sec5.91*10-6secSqrt(n)4.47 * 10-6sec6.32* 10-6sec7.75*10-6secn20 *10-6sec40*10-6sec60* 10-6secn log2n86 * 10-6sec213*10-6sec354*10-6secn?400*10-6sec1600*10-6sec3600*10-6secn40.16sec2.56sec12.96sec2nn!CS3381Des&AnalofAlg(2001-2002SemA)CityUnivof HK/DeptofCs/HelenaWong2.AnalysisofAlgorithms-4
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 4 Asymptotic performance Assume: an algorithm can solve a problem of size n in f(n) microseconds (10-6 seconds). f(n) n=20 n=40 n=60 Log2n Sqrt(n) n n log2n n 2 n 4 2 n n! 5.32 * 10-6 4.32 * 10 sec -6sec 5.91 * 10-6sec 6.32 * 10-6 4.47 * 10 sec -6sec 7.75 * 10-6sec 40 * 10-6 20 * 10 sec -6sec 60 * 10-6sec 213 * 10-6 86 * 10 sec -6sec 354 * 10-6sec 1600 * 10-6 400 * 10 sec -6sec 3600 * 10-6sec 0.16 sec 2.56 sec 12.96 sec
Asymptotic performanceAssume: an algorithm can solve a problem of size n in f(n)microseconds (10-6 seconds).f(n)90000log2n80000Sqrt n70000n60000nlog2n50000n24000030000n4200002n10000n!nCS3381Des&AnalofAlg(2001-2002SemACityUnivof HK/Deptof CS/Helena Wong2.AnalysisofAlgorithms-5
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 5 microseconds f(n) log2n Sqrt n n nlog2n n 2 n 4 2 n n! 10000 20000 30000 40000 50000 60000 70000 80000 90000 n Asymptotic performance Assume: an algorithm can solve a problem of size n in f(n) microseconds (10-6 seconds)