Computer Science 308-250B

EXTRA problems on Big-*O* notations

S O L U T I O N S

Show the following

f_{n} **is** O(2^{n}) (where f_{n} is the n^{th} Fibonacci number)

By mathematical induction. f_{n} **< **2^{n}

**Basis:** f_{1} = 1 < 2 = 2^{1} , f_{2} = 1 < 4 = 2^{2}

Induction step:

Let n>2. Assume f_{n-2} **< **2^{n-2} and f_{n-1} **< **2^{n-1}

f_{n} = f_{n-1} **+** f_{n-2} **< **2^{n-1}** + **2^{n-2}** **= 3*2^{n-2 }< 4*2^{n-2}** = **2^{n} .

n^{k} **is** O(n^{log log n}) for any k>0

n^{k} **< **n^{log log n} iff k < log log n iff n >

By setting n_{0} = , we conclude n^{k} **is** O(n^{log log n})

for any k>0

a^{n} **is not** O(n^{k}) for any k>0, a>1

By the limit rule.

Lim_{n->}• n^{k}/a^{n}

= Lim_{n->}• kn^{k-1}/(ln a)a^{n}

= Lim_{n->}• k(k-1)n^{k-2}/(ln a)^{2}a^{n}

…

= Lim_{n->}• k(k-1)(k-2)…1/(ln a)^{k}a^{n}

= Lim_{n->}• k!/(ln a)^{k}a^{n }= 0

which implies

n^{k} **is **O(a^{n}) for any k>0, a>1

a^{n} **is not** O(n^{k}) for any k>0, a>1

log n! **is** q(n log n) (log n! **is** W(n log n) and **is** O(n log n))

Notice that log n! = S_{i=1..n} log i < S_{i=1..n} log n = n log n.

Also S_{i=1..n} log i > S_{i=n/2..n} log i > S_{i=n/2..n} log n/2 = n/2 log n/2.

The results follow.

whenever m>k, n^{k} **is** O(n^{(m-}e)), for some small enough e>0

Set e = (m-k)/2 > 0. Note that m-e = (m+k)/2 > k, since m>k.

Thus n^{k} **is** O(n^{(m-}e)).

whenever m<k, n^{k} **is** W(n^{(m+}e)), for some small enough e>0

Set e = (k-m)/2 > 0. Note that m+e = (k+m)/2 < k, since m<k.

Thus n^{k} **is** W(n^{(m+}e)).

Solve the following recurrences and express your solution with the big-q notation:

We consider the general case

by comparing the special function to f(n):

a=1, b=2, f(n)=bn

= 1 **is** O(bn^{1-e}) for small enough e>0

and thus by the Master Method (3)

T_{A}(n) **is** Q(f(n)) = Q (n)

a=1, b=2, f(n)=bn^{2}

= 1 **is** O(bn^{2-e}) for small enough e>0

and thus by the Master Method (3)

T_{B}(n) **is** Q(f(n)) = Q (n^{2})

a=9, b=3, f(n)=n^{2 }log n+n+2

= n^{2} and thus log n = n^{2} log n **is** Q(n^{2 }log n+n+2)

and thus by the Master Method (2)

T_{C}(n) **is** Q(log^{2} n) = Q(n^{2} log^{2} n)