Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithm Efficiency Analysis, Complexity Time is related to the number of…
Algorithm Efficiency Analysis
Worst-case efficiency
Longest running time
Best-case efficiency
Shortest running time
Average-case efficiency
Average running time
big 'O' notation
O(1)
constant function
O(log n)
complexity increases slowly as problem size increase
O(n)
complexity increases linearly with size of input
O(n^2)
Quadratic increase
O(n log n)
complexity increases a little faster than O(n)
Divide problem into sub problems that are solved the same way
O(n^3)
Cubic increases
O(2^n)
Exponential increase, unmanageable for any meaningful n
Eg. Find all subsets of a set of n elements
Practically by experiment
Implement the algorithms in any programming language and run the programs
Depend on compiler, computer, data input and programming style
Complexity Time is related to the number of steps
Count the number of steps and then find the class of complexity
Find the complexity time for each steps and then total up
Theoretically by calculation