It is a measure of how an algorithm responds to a data size.
It classifies performance as input size grows. “O” indicates the order of operation: time scale to perform an operation
Many algorithm and DS have more than an O
- Inserting
- Searching
| Notation | Description | Example |
|---|---|---|
| O(1) | Constant Time | Looking up a single element in an array |
| O(log n) | Logarrithmic | Finding an item is a sorted array with a binary search |
| O(n) | Linear time | Searching an unsorted array for a specific value |
| O(n log n) | Log linear | Complex sorting algorithm like heapsort and merge sort |
| O(n2) | Quadratic | Simple sorting algorithm like bubble sort |