Asymptotic Notation

2026-11-18

notes / Algorithms-1

Algorithms-1


Hard Method

Insertion Sort (A) cost times
for j = 2 to A.length c1 n
key = A[j] c2 n−1
i = j - 1 c3 n−1
while i > 0 && A[i] > key c4 ∑j=2ntj
A[i+1] = A[i] c5 ∑j=2n(tj−1)
i = i - 1 c6 ∑j=2n(tj−1)
A[i+1] = key c7 n−1

tj is the number of times the while loop repeats for every value of j

Total Cost: ∑cost*time

T(n)=c1n+c2(n−1)+c3(n−2)+c4∑j=2ntj+c5∑j=2n(tj−1)+c6∑j=2n(tj−1)+c7(n−1)

Then analyse

Finally express T(n) in the most general form you can e.g. as a quadratic an2+bn+c you can then say T(n) is a quadratic function of n


O(n),Θ(n),Ω(n) Notation

Θ(g(n))={f(n):∃c1,c2,n0∈Z+, such that 0≤c1g(n)≤f(n)≤c2g(n)∀n≥n0}

O(g(n))={f(n):∃c1,n0∈Z+, such that 0≤f(n)≤c1g(n)∀n≥n0}

Ω(g(n))={f(n):∃c1,n0∈Z+, such that 0≤c1g(n)≤f(n)∀n≥n0}

in equality and inequalities

2n2+3n+1=2n2+Θ(n)=Θ(n2)

comparing functions

  1. f(n)=Θ(g(n)) and g(n)=Θ(h(n)) implies f(n)=Θ(h(n))
    1. this is true for O and Ω as well
  2. f(n)=Θ(f(n))
    1. also true for O and Ω

Standard Functions

Polynomials

asymptotically positive polynomial (ad>0) ⟹ p(n)=Θ(nd)

exponential

|x|<1⟹ex=Θ(n2)


Examples

2024MA

Q1

T(n)=3T(n/4)+nlogn

Q2

T(n)={2n≤2nT(n)+nn>2