Question

1. Let f(n) = 5n^2. Prove that f(n) = O(n^3).

2. Let f(n) = 7n^2. Prove that f(n) = Ω(n).

3. Let f(n) = 3n. Prove that f(n) =ꙍ (√n).

4. Let f(n) = 3n+2. Prove that f(n) = Θ (n).

5. Let k > 0 and c > 0 be any positive constants. Prove that (n + k)c = O(nc).

6. Prove that lg(n!) = O(n lg n).

7. Let g(n) = log10(n). Prove that g(n) = Θ(lg n). (hint: ???? ? = ???? ?)???? ?

8. Use the mathematical induction to show that ∑? 2i = 2?+1 − 1.i=0

9. Use the mathematical induction to show that the solution for T (n) = T (⌊?⌋) + n2 is O(n2), note2

   that T(0) = 0.

10. Use the master method to give a tight asymptotic bound for T (n) = 2T (n/4) + n.

let lg n denote log2 n.

Answer 1

1) f(n) = 5n^2

required to prove that f(n) = O(n^3)

let k(n) = a * n^3.

a can be any positive constant.

k = 10 *n^3.

let n be equal to 1

f(1) = 5 k(1) = 10

f(2) = 20 k(1) = 80

....

in any case the value of f(n)<=k(n).

so f(n) = O(n^3).

2)

Given f(n) = 7n^2.

Required f(n) = (n).

to prove we need to have

n <= c*f(n), here c is a positive constant

n <= c*7n^2

for n=0

0= 0.

for n=1

1 <= c*7

c >= 1/7

so by this we can say that for any value of c above 1/7 can make the statement f(n) = (n) true any one value of c is sufficient to prove the statement.

3)

Given f(n) = 3n.

required to prove f(n) = ()

we know that for every k <=

equality case comes only for k=1. So for a positive constant say c.

c.k <  

here c >1.

so lets take it as 3

3.k <

3.n <

by this we can say that

f(n) = ().

4)

Given f(n) = 3n+2

and require to prove that f(n) = .

we require that c1.n < 3n+2 < c2.n (c1> 0, c2>0, n0>0 for all n>n0)

here c1 and c2 can be any positive integers.

any one value of c1 and c2 is enough to prove f(n) =

if c1 = 1

n < 3n+2

for n= 0

0 < 2

for n = 1

1 < 5

....

for all values of n it is true.

so c1 =1 can be considered.

3n+2 < c2.n

here we should not consider the case n = 0,because n>n0 and n0>0 (which is assumption).

let n = 1.

3(1)+2 < c2.1

5<c2.

c2>5.

for any value c2>5 the case is true. So let us say c2 = 6.

for the pair of c1= 1 and c2 = 6 the case is true so, we can say  f(n) = .

5)

(n+k)c = O(nc) for k>0 and c>0

lets assume it as true

so

(n+k)c <= t *(nc)

here t is a positive number.

let n=1, k= 1, c=1

(1+1)1 <= t *(1)

2<= t

so it true for all t>=2.

if it is true for one case then the statement (n+k)c = O(nc) k>0, c>0 is considered true.

6)

Given log2(n!) = O(nlog2(n)).

for it to be true

log2(n!) <= c. (nlog2(n)).

log2(n!) <= c.(log2(n^n)).

let say c=1.

log2(n!) <= log2(n^n)

by removing log2 on both sides, we can see that

n! < = n^n

which is always true so the statement log2(n!) = O(nlog2(n)) is true.

7)

Given g(n) = log10(n).

g(n) = Θ(lg n).

this is true because

c1.log10(n) < log2(n) < c2.log10(n)

c1>0, c2>0, n>0.

log10(n^c1) < log2(n) < log10(n^c2)

here we need to find c1 and c2 values to prove the statement, which can be done by taking some examples.

8)

the question ∑? 2i = 2?+1 − 1.i=0 is quite ambiguous

9)

as the part details of T (⌊?⌋) is not mentioned properly.

considering it as,

t(n) = t(n) + n2

n2=0.

and t(n) = 0.

this is clearly t(n) = O(n2).  

the answer is same even if ⌊?⌋ is considered as step function.

10)

according to master theorm

T(n) = Θ(n^log4(1)).

T(n) = Θ(n^0).

T(n) = Θ(1).