O W Q Limits

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

2. Show that n³+n²= W(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)= W(n²)

0 ≤ cWg(n) ≤ h(n)

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

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

0 ≤ cW ≤ ½-½/n

0 ≤ cW ≤ ½-1/2n         for cW=¼ > 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)= Q(n²)

We have shown:

½n(n-1)= W(n²) for c_W=¼ > 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 Q:

c_Wg(n) ≤ h(n) ≤ c_Og(n)

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

½n(n-1)= Q(n²) for c_O=½, c_W=¼ and n₀=2