O W Θ Limits

1. Show that n is in O(n²)

2. Show that n³+n²= Ω(n²)

0 ≤ cg(n) ≤ h(n)

0 ≤ cn2 ≤ n3+n2

0/n2 ≤ cn2/n2 ≤ n3+n2/n2

0 ≤ c ≤ n+1

0 ≤ 2 ≤ 2        with c=2 and n0=1

3. Show that ½n(n-1)= Ω(n²)

0 ≤ cΩg(n) ≤ h(n)

0 ≤ cΩn2 ≤ ½n(n-1) = ½n2-½n

0/n2 ≤ cΩn2/n2 ≤ (½n2-½n)/n2

0 ≤ cΩ ≤ ½-½/n

0 ≤ cΩ ≤ ½-1/2n         for cΩ=¼ > 0 and n0=2

4. Show that ½n(n-1)= O(n²)

0 ≤ h(n) ≤ cOg(n)

0 ≤ ½n(n-1) = ½n2-½n ≤ cOn2

0/n2 ≤ (½n2-½n)/n2 ≤ cOn2/n2

0 ≤ ½-½/n ≤ cO

0 ≤ ½-1/2n ≤ cO         for cO=½  and n0=1 because 1/2n → 0 as n→∞

5. Show that ½n(n-1)= Θ(n²)

We have shown:

½n(n-1)= Ω(n²) for c_Ω=¼ > 0 and n₀=2

¼n² ≤ ½n(n-1)

½n(n-1)= O(n²) for c_O=½  and n₀=1

½n(n-1) ≤ ½n²

By definition of Θ:

c_Ωg(n) ≤ h(n) ≤ c_Og(n)

¼n² ≤ ½n(n-1) ≤ ½n²

½n(n-1)= Θ(n²) for c_O=½, c_Ω=¼ and n₀=2