Question

Given below list of functions:

f_{1 =} (4/3)ⁿ,

f2 = 2²⁽ⁿ⁺¹⁾,

f3 = 2ⁿ,

f_{4 =} 42⁴²log₂n,

f5 = n²,

f6 = 4^log₂n,

f7 = 2²ⁿ,

f8 = (1/2)ⁿ

Order them in ascending order so that f_i = Ω(f_i+1)

Answer 1

To arrange a function in ascending order we take higher value of n and see which function is giving highest value

here clearly f8 is smallest because it is tending to 0 as n is increasing

also f1<f2 because 4/3 = 1.33 but f2 is 4^(n+1)

also f2>f3 because f2 = 4^(n+1) and f3 is 2^n

also f1<f3

now f4 is 42^42(logn) this is a function of O(logn) because 42^42 is constant

so if we take very high value of n then

42^42*logn < (4/3)^n < 2^n < 2^(2(n+1))

now f5 is n^2 which is greater than f4 but less than all other 3

now f6 is 4^logn we compare it with 42^42*log(n) clearly the growth rate of 4^logn is greater hence it is bigger than 42^42*log(n)

f7 = 2^(2n) which is 4^n which is same as function 2^2(n+1)

so in ascending order we get

f8 < f4 < f6 < f5 < f1 < f3 < f7 < f2