Computer Science 308-250B

EXTRA problems on Big-O notations

S O L U T I O N S

 

 

Show the following

fn is O(2n) (where fn is the nth Fibonacci number)

By mathematical induction. fn < 2n

Basis: f1 = 1 < 2 = 21 , f2 = 1 < 4 = 22

Induction step:

Let n>2. Assume fn-2 < 2n-2 and fn-1 < 2n-1

fn = fn-1 + fn-2 < 2n-1 + 2n-2 = 3*2n-2 < 4*2n-2 = 2n .

 

nk is O(nlog log n) for any k>0

 

nk < nlog log n iff k < log log n iff n >

By setting n0 = , we conclude nk is O(nlog log n)

for any k>0

 

an is not O(nk) for any k>0, a>1

 

By the limit rule.

Limn->• nk/an

= Limn->• knk-1/(ln a)an

= Limn->• k(k-1)nk-2/(ln a)2an

…

= Limn->• k(k-1)(k-2)…1/(ln a)kan

= Limn->• k!/(ln a)kan = 0

which implies

nk is O(an) for any k>0, a>1

an is not O(nk) 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! = Si=1..n log i < Si=1..n log n = n log n.

Also Si=1..n log i > Si=n/2..n log i > Si=n/2..n log n/2 = n/2 log n/2.

The results follow.

 

whenever m>k, nk 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 nk is O(n(m-e)).

 

whenever m<k, nk 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 nk 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(bn1-e) for small enough e>0

and thus by the Master Method (3)

TA(n) is Q(f(n)) = Q (n)

 

 

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

= 1 is O(bn2-e) for small enough e>0

and thus by the Master Method (3)

TB(n) is Q(f(n)) = Q (n2)

 

 

a=9, b=3, f(n)=n2 log n+n+2

= n2 and thus log n = n2 log n is Q(n2 log n+n+2)

and thus by the Master Method (2)

TC(n) is Q(log2 n) = Q(n2 log2 n)