Big O

• f(n) = O(g(n))
• 0 ≤ f(n) ≤ cg(n) for any positive constance c, n ≥ n₀

Small o

• f(n) = O(g(n))
• 0 ≤ f(n) < cg(n) for any positive constance c, n ≥ n₀

Big Ω

• f(n) = Ω(g(n))
• 0 ≤ cg(n) ≤ f(n) for any positive constance c, n ≥ n₀

Small ɷ

• f(n) = ɷ(g(n))
• 0 ≤ cg(n) < f(n) for any positive constance c, n ≥ n₀

Θ

• f(n) = Θ(g(n))
• 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for any positive constance c₁ and c₂, n ≥ n₀

def func(n):
    a=5 # 1 time
    b=6 # 1 time
    c=10 # 1 time

    for i in range(n):
        for j in range(n):
            x = i * i # n^2 times
            y = j * j # n^2 times
            z = i * j # n^2 times

    for k in range(n):
        w = a*k + 45 # n times
        v = b*b # n times

    d = 33 # 1 time

# Run times
#  1 + 1 + 1 + n^2 + n^2 + n^2 + n + n + 1
# = 3*n^2 + 2*n +4

# O(n^2)
            

Problem Solving with Algorithms and Data Structures using Python

Big O Cheat Sheet