Guessing complexity based off problem size

Size Complexity
7 \(O(N!)\)
12 \(O(2^N)\)
16 \(O(N^3)\)
64 \(O(N^2)\)
462 \(O(NlogN)\)
4096 \(O(N)\)
\(2^4096\) \(O(logN)\)
Any \(O(1)\)

Greatest Common Deviders

def gcd(a, b):
    while b:  a, b = b, a % b
    return a

Longest Increasing Subsequence

def lis(nums):
    tails = []
    for num in nums:
        i = bisect_left(tails, num)
        if i == len(tails): tails.append(num)
        else:               tails[i] = num
    return len(tails)

Two Pointers Technique

Same sequence

Opposite direction

Two sequences

Linked List

Example Questions