Familiarity with Big O
We want to be familiar with Big O for typical algorithms:
- Given a description of a task, guess its Big O.
``First you sort the input, which is n*log(n), then ...''
- Predict how well an algorithm will scale up.
``Now that my new web service is the hottest thing in the CS
Department, will it scale up to every college in the country
so I can take it public and make my first billion dollars?''
- Given a program that is too slow, figure out what is wrong.
``The sorting step is taking O(n2) time; that's pathetic.''
- Select algorithms based on data sizes and Big O.
``This set could be large, so we need O(log(n)) lookup ...''