Big-O Complexity
Algorithms
Course templates · Computer science
The basics behind most programming courses and technical interviews: Big-O, data structures, everyday Git and HTTP status codes.
4 study sets · 50 cards · 2 pages of study notes
Algorithms
Data structures
Version control
Web development
This course has two halves. The first is theory you need for data structures classes and technical interviews; the second is practical knowledge you need for any programming job or project.
Theory first: Big-O Complexity, then Data Structures at a Glance. Learn Big-O first, because every data structure card describes its operations in Big-O terms. For each data structure, make sure you can say what it is good at and what it is bad at.
Then the practical half: Everyday Git Commands and HTTP Status Codes. These stick best when you use them, so keep a small project going while you study, commit to Git often, and try each command on it.
Flashcards help you recall the facts. Understanding comes from writing code: implement a stack, a queue and a hash table yourself, and time a few algorithms on large inputs to see the growth rates for real.
Add your own: put your lecture notes and assignment specs in this course, and ask the tutor to quiz you on them.
Big-O describes how running time or memory grows as the input grows. It ignores constants and smaller terms, so 3n² + 5n + 2 is O(n²). For a loop, count how many times the body runs: one loop over n items is O(n); a loop inside a loop over the same items is O(n²); halving the problem each step, as in binary search, is O(log n).
Unless a question says otherwise, Big-O usually means the worst case. Some structures differ a lot between cases: a hash table lookup is O(1) on average but O(n) in the worst case, when many keys collide.
Choosing a data structure. Ask which operation you will do most.
- Look up by position: an array, O(1).
- Look up by key: a hash table, O(1) on average.
- Keep items in sorted order with fast inserts: a balanced binary search tree, O(log n).
- Always take the smallest or largest next: a heap.
- Last in, first out, such as undo: a stack. First in, first out, such as a print queue: a queue.
Git. A commit is a snapshot of your project. Stage the changes you want with git add, then save them with git commit. Work on a branch for each change, and merge it back when it is done. Never rewrite history that others already have: use git revert rather than git reset on a shared branch.
HTTP status codes are grouped by their first digit. 2xx means success, 3xx means redirect, 4xx means the client made a mistake (bad request, not logged in, not allowed, not found), and 5xx means the server failed. 401 means not authenticated; 403 means authenticated but not allowed.