# Runtime Overview

If we are given hints on the runtime requirement of a problem during interviews, we can roughly deduce the algorithm as follows.

`O(1)`

Constant time complexity. Could be

- Hashmap lookup
- Finding and applying math formula

`O(log(N))`

`log(N)`

grows VERY slowly. `log(1,000,000)`

is only about `20`

. In fact, lookup by primary key in a relational database is `log(N)`

(many mainstream relational databases such as postgres use B-trees for indexing by default, and search in B-tree is `log(N)`

).

In coding interviews, `log(N)`

typically means

- Binary search or variant
- Balanced binary search tree lookup

`O(N)`

Linear time normally means looping through a linear data structure a constant number of times. Most commonly this means

- Going through array/linked list
- Two pointers
- Some types of greedy
- Tree/graph traversal
- Stack/Queue

`O(K log(N))`

- Heap push/pop
`K`

times. When you encounter problems that look for the "top K elements", you can usually solve them with pushing and popping to a heap,`K`

times, resulting in`O(K log(N))`

runtime. e.g., K closest points, merge K sorted lists. - Binary search K times.

`O(N log(N))`

- Sorting. The default sorting algorithm's expected runtime in all mainstream languages is
`N log(N)`

. For example, java uses a variant of merge sort for object sorting and a variant of quick sort for primitive type sorting. - Divide and conquer with a linear time merge operation. Divide is normally
`log(N)`

, and if merge is`O(N)`

then the overall runtime is`O(N log(N))`

. An example problem is smaller numbers to the right.

`O(N^2)`

Also called quadratic time.

- Nested loops, e.g., visiting each matrix entry
- Many brute force solutions

For small `N < 1000`

, this is actually not that bad for modern computers. In fact, you can probably pass most Leetcode tests with quadratic time for small `N`

s. However, in an interview, your solution usually has to do better than quadratic time to impress the interviewer if there is a better solution.

`O(2^N)`

Grows very rapidly. Often requires memoization to avoid repeated computations and reduce complexity.

- Combinatorial problems, backtracking, e.g. subsets

`O(N!)`

Grows insanely rapidly. Only solvable by computers for small `N`

. Often requires memoization to avoid repeated computations and reduce complexity.

- Combinatorial problems, backtracking, e.g. permutations