CODEWITHSUNDEEP
algorithmtime-complexity
bigbong
bigbong

Reputation: 561

What will be the asymptotic time complexity of the following function?

I came across this problem on asymptotic complexity of a function:

The complexities of 3 functions are as follows:

f(n) = O(n)

g(n) = Big-Omega(n)

h(n) = Theta(n)

So what will be the asymptotic complexity of the resultant function [f(n).g(n)] + h(n)

I can figure out the answer to this will be Big-Omega(n) by elementary hit and trial. For example if I say f(n) = n and g(n) = n and h(n) = n. So we can say f(n) is O(n) and g(n) is Big-Omega(n) and h(n) is Theta(n). Now f(n).g(n) is n2 and this will be Big-Omega(n) but not O(n). Now adding this to h(n) is n2+n. Which also is Big-Omega(n) but not Theta(n).

But I'm not able to figure out a proper logical or mathematical proof to this. Can someone please help me out with this?

Upvotes: 1

Views: 445

Answers (1)

Ron Teller
Ron Teller

Reputation: 1890

Here's an attempt at a logical explanation:

  • f(n) = O(n) means that f's running time is at most linear (may be constant time).
  • h(n) = Theta(n) means that h's running time running is linear.
  • g(n) = Big-Omega(n) means that g's running time is atleast linear (may be polynomial, exponential... we don't know).

Now let's analyse the best case: f(n) is constant time, g(n) is linear, h(n) is linear. what can we say about the function f(n)*g(n)+h(n)? that it's also linear.

What can we say about the worst case? nothing, as we have no clue about the behaviour of g(n) in the worst case.

So we can conclude that f(n)*g(n)+h(n) = Big-Omega(n) as this function is linear at the best case.

Upvotes: 1

Related Questions