CP164 Lecture Notes - Lecture 10: Binary Search Algorithm, Quadratic Equation, Linear Search
Document Summary
We have to have a way of comparing our algorithms to see which ones are the most efficient. So much going on with input and output outside the algorithm. Want to do something independent to execution ( user input) Need to look at the rate of growth of execution time. Execution time is directly proportional to the input size. If we triple the amount of data we triple amount of comparisons. A linear search is called because the amount of work grows at a linear rate. Meanwhile a binary search grows at binary rate. When doing search we can never do a constant search. Throw away constant terms in quadratic equation of runtime. Increases by four times o(n^2) has an order of n^2 time complexity. If algorithm has a single loop and after the first iteration the amount of data left to process is n/2 (or n/k) that is o(log n) Basically loop can ignore half of elements.
