CODEWITHSUNDEEP
algorithmtime-complexityasymptotic-complexity
Devasish
Devasish

Reputation: 1957

asymptotic notation on both side of equation

I know what does f(n)=theta(g(n)) or f(n)=BighOh(g(n)) mean but getting confused when there are something like theta(f(n)) = theta(g(n)). i.e. when the asymptotic notation is on the both side. Can anyone please explain what does this mean?

I got this, when solving a problem like this: there are 3 algorithm

X : is polynomial
Y : is exponential
Z : is double exponential

There are 4 opitions in the answers : 

a) theta(X) = theta(Y)
b) theta(X) = theta(Z)
c) theta(Y) = theta(Z)
d) BigOh(Z) = X

The correct answer is option C. Can anyone please explain

Upvotes: 0

Views: 91

Answers (1)

sameerkn
sameerkn

Reputation: 2259

C = θ(D), in simple language means there are 2 tight bounds say, A and B such that C can be sandwiched between them. That is A <= C <= B.

A and B depend upon D. That is, A = aD and B = bD where, a and b are constants.

In general theta(P) = theta(Q) means the bounds specified by P (aP and bP) and Q (aQ and bQ)

  • are equal i.e, aP = aQ and bP = bQ, or

  • one of the bounds in contained inside another i.e, aP<=aQ<=bQ<=bP or aQ<=aP<=bP<=bQ.

    Y = exponential = 1.5^x
Z = double exponential = 1.5^1.5^x

Here, it can be seen from the the graph that the bounds on exponential function (1.5^x) can contain the bounds of double exponential function (1.5^1.5^x). Hence θ(Y) = θ(Z). In fact the bounds of exponential function can be used as bounds of double exponential function.

Upvotes: 1

Related Questions