Infer Algorithm By Time Complexity

Introduction

Sometimes we need to infer algorithms by time complexity. After we bring out the brute force solution, the interviewer may ask: Can you solve by time complexity of O(xxx)? We don’t always know what’s the optimal solution, but we may infer the algorithm based on the desired time complexity.

O(logn)

Binary Search

O(√n)

Prime Factorization

O(n)

Two Pointers

Monotonic Stack

Enumeration

O(nlogn)

Sort

Data Structure Operation (e.g. Heap)

O(n^2), O(n^3)

Dynamic Programming

O(2^n)

Combination

O(n!)

Permutation