CODEWITHSUNDEEP
algorithmbig-o
user4780686
user4780686

Reputation:

Big-O Notation Exponential time

Suppose we have an algorithm that uses two functions and both functions run in O(C^n) where C equals an array of x size and n equals an inner array of y size.

Can we just say that O(C^n) + O(C^n) = O(C^n) when we are talking about time complexity or should we write the whole thing?

Upvotes: 0

Views: 1089

Answers (2)

anukul
anukul

Reputation: 1952

O(C^n) + O(C^n) = O(C^n)

We only care about the most significant portion of the complexity, so constants are not usually taken into account in Big O notation.

Read more about it in the Related links on the right.

Upvotes: 3

Edward Peters
Edward Peters

Reputation: 4062

I think you miswrote your O time - didn't you mean O(x^y)?

Apart from that, though, Big-O time is ambivalent to constant factors, and addition of two functions will (more or less, modulo weird non-converging things) always be less than twice the larger function. So no, you don't have to write the full thing - O(f(x)) + O(g(x)) = max(O(f(x)), O(g(x))).

Upvotes: 0

Related Questions