A set of steps or instructions for completing a task.
- Clearly defined problem statement with input and output;
- The steps in the algorithm need to be in a very specific order;
- The steps also need to be distinct;
- The algorithm should produce a result;
- The algorithm should finish in a finite amount of time.
Breakes down a problem into steps identiyfing what data structure is best for the task.
Way of showing how the runtime of a function increases as the size of input increases.
How long it takes to complete a task.
It deals with the amount of memory taken up on the computer.
Theoretical definition of the complexity of an algorithm as a function of the size.
It means the order of magnitude of complexity.
"Upper bounds" because it measures how the algorithm performs in the worst case scenario.
| Notation | Description | Example |
|---|---|---|
| O(1) | constant time | Access item of array at a given position/index |
| O(logn) | logarithmic time | Binary Search |
| O(n) | linear time | Linear Search |
| O(nlogn) | Quasilinear time | Merge Sort |
| O(n^2) | quadratic time | Brute Force |
| O(n^3) | cubic time | Brute Force |