In 13 the w is little omega Prove or disprove 42n omega4n W

In 13, the \'w\' is little omega.

Prove or disprove: 4^2n = omega(4^n). What is the growth of n^2 + 2n^2 + 3n^2 + ... + n^4?

Solution

Answer:

13- For little omega :

w(g(n)) = f(n) if

0 <= c*g(n) < f(n)

We have given f(n) = 4^2n , , g(n) = 4^n

now put it in the definition

0 < = c* 4^n < 4^2n

put c = 1 and n = 1

0 < = 1 x 4^1 < 4^2*1

now it is clear here that g(n) < f(n)

therefore 4^2n = w(4^n)

14 - n^2 + 2n^2 + 3n^2 + . . . +n^4

take n^2 common , we get

n^2 ( 1 + 2 + 3 + .... + n^2

n^2 [ n^2(n^2 - 1)/2) ]

= n^2 [ n^4 - n^2]/2

= n^6 + n^4 / 2

Hence growth is n^6