Summary
Stuff you should know
Big O is a way for us to check the efficiency of our program. Theta and Omega are different bounds, Omega being the best case, and Theta being the bound when O and Omega are the same. Big O is the worst case. Computer programmers mostly care about Big O, and want to know about space and time complexity.
There are 7 common runtimes: O(1), O(lg n),O(N) O(N lg N),O(N^2), O(2^N) and O(N!). NP complete is a type of problem that cannot be solved quickly, but the answer can be determined to be correct quickly.
If you don't know this, go back and reread. Try flashcards, I have heard they are helpful for....people like you.
Questions
- What are Big O, Theta, and Omega? Examples? When do you use Theta?
- What is a step?
- Name the runtimes. Which one is associated with sorting?
- Give an example of an NP Complete problem?
- Is O(N) or O(1) better?
- What is NP complete? How does it differ from P?