determine whether the following pair of functions are in sam

determine whether the following pair of functions are in same order 2x+1 9x-5 i.e big theta

Solution

Theta(g(n)) = { f(n) : there exists positive constants c1,c2 and n1 such that 0<=c1(g(n))<=f(n)<=c2(g(n)) for all n>=n1 }

for f(x) = 2x + 1 we have big Theta = g(x) = x because

0 <= 1.x <= 2x + 1 <= 3.x for all x>=1

hence Big Theta of 2x + 1 = x

for f(x) = 9x-5 we have big Theta = g(x) = x because

0 <= 1..x <= 9x-5 <= 10.x for all x >= 5/8

hence Big Theta of 9x-5 = x

hence both pair of functions are of same order of big Theta i.e. x