CS 111 - 4/29/14
Final Exam - Wednesday 5/7/14 at 3:30pm in LC C3
Format of the final will be same as the other exams
20 multiple choice question
2 write method
Run Time of Algorithms
- We can have two algorithms that solve the
same problem, but is one better than another?
Common Run Times for amount of data
O(1)
O(log n)
O(n)
O(n * log n)
O(n * n) == O(n^2)
O(n * n * n)
O(2^n)
Sorting
Selection Sort:
general idea: select the smallest and move
it to the front of the array
O(n * n) algorithm
QuickSort:
general idea: select a pivot value
move values smaller than pivot to the front
while moving values larger than pivot to
the back
repeat on each portion on either side of the
pivot
O(n * log n) algorithm