CODEWITHSUNDEEP
algorithmcomplexity-theory
vaishali jhalani
vaishali jhalani

Reputation: 91

Complexity analysis after multiplication of two functions

Given F(n) = θ(n)

H(n) = O(n)

G(n) = Ω(n)

then what will be order of F(n) + [G(n) . H(n)] ?

edit: F(n) = θ(n) not Q(n)

Upvotes: 4

Views: 387

Answers (1)

chepner
chepner

Reputation: 531918

There isn't enough information to say anything about the function P(n) = G(n)*H(n). All we know is that G grows at least linearly; it could be growing quadratically, cubically, even exponentially. Likewise, we only know that H grows at most linearly; it could only be growing logarithmically, or be constant, or even be decreasing. As a result, P(n) itself could be decreasing or increasing without bound, which means the sum F(n) + P(n) could also be decreasing or increasing without bound.

Suppose, though, that we could assume that H(n) = Ω(1) (i.e., it is at least not decreasing). Now we can say the following about P(n):

P(n) = H(n) * G(n)
     >= C1 * G(n)
     = Ω(G(n)) = Ω(n)

P(n) <= C1*n * G(n)
      = O(n*G(n))

Thus F(n) + P(n) = Ω(n) and F(n) + P(n) = O(n*G(n)), but nothing more can be said; both bounds are as tight as we can make them without more information about H or G.

Upvotes: 2

Related Questions