What is the purpose of algorithm analysis?
To compare the effectiveness of algorithms without having to consider implementation details, the speed of the computer system used, and test data. As n grows, how does the number of operations grow?
How do you analyze the speed of an algorithm?
- count the number of steps or operations needed
- look at it as a function of the size of the problem
- you can look at either the average number of steps, or the
maximum number of steps
What is the speed of a linear search?
O(n)
What is the speed of a binary search?
O(log(n))
What happens when you double n with the different typical bounds?
O(log n): adds c to time
O(n): double the time
O(nlogn): not much slower than O(n)
O(n^2): time4
O(n^3): time8
O(2^n): time^2
O(n!): don’t even try
What is the speed of an ordered insert?
O(n): only one loop, goes through one element at a time, essentially a linear search
What is the speed of our simple sorting algorithms?
O(n^2): contains two nested loops
What is an example of a better sorting algorithm?
Merge sort:
- split the array into two small arrays
- sort the two halves (using two merge sorts)
- merge the two sorted halves into a sorted array after the
2 merge sorts have returned
What is the speed of a merge sort?
O(nlogn)
