CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Sanjay Verma
Sanjay Verma

Reputation: 101

Asymptotic analysis of function

How to understand this type of question, I know about big-O, big-omega and big-theta but can you explain with the example.

PS: 1. Big-o- It defines the upper bound of an algorithm or in layman terms we can say that for calculating the worst case, we use big-oh.

DEFN: f(n)<= cg(n) where c is constant and greater than 0. for example: for some algorithm if it's worst case is O(n) then O(n^2) will also it's upper bound but we're only interested in tightest upper bound.Right?

  1. Big-omega- It defines the lower bound or best case of an algo. DEFN: f(n)>=cg(n)

similarly for Big-theta i.e average case of an algo.

Upvotes: 2

Views: 170

Answers (1)

amit
amit

Reputation: 178431

Assuming functions are strictly positive and growing functions, the answer is Omega(n)

Let's define bounds for all our function:

  • f(n) >= c1*n - due to being Omega(n)
  • We have no knowledge of any upper bound for f(n).
  • g(n) >= CONST - since it's growing and non negative
  • g(n) <= c2*n - due to being O(n)
  • c3n <= h(n) <= c4n - due to being Theta(n)

Now let's look for lower bound (Omega):

T(n) = [f(n) * g(n)] + h(n) >= [c1*n * CONST] + c3*n
     = [c1*CONST + c3]*n

And we see that indeed T(n) is in Omega(n)

Now, if we try to find an upper bound, and let this bound be some function phi(n) we can have f(n) = phi(n) * n, which is still in Omega(n) and then:

T(n) = [phi(n)*n * g(n)] + h(n) >= [phi(n)*n * CONST] + c3*n

And this is in Omega(phi(n)*n) - and thus cannot be in O(phi(n))

Upvotes: 1

Related Questions