3

Imagine T1(n) and T2(n) are running times of P1 and P2 programs, and

T1(n) ∈ O(f(n))

T2(n) ∈ O(g(n))

What is the amount of T1(n)+T2(n), when P1 is running along side P2?

The Answer is O(max{f(n), g(n)}) but why?

2 Answers 2

4

When we think about Big-O notation, we generally think about what the algorithm does as the size of the input n gets really big. A lot of times, we can fall back on some sort of intuition with math. Consider two functions, one that is O(n^2) and one that is O(n). As n gets really large, both algorithms increases without bound. The difference is, the O(n^2) algorithm grows much, MUCH faster than O(n). So much, in fact, that if you combine the algorithms into something that would be O(n^2+n), the factor of n by itself is so small that it can be ignored, and the algorithm is still in the class O(n^2).

That's why when you add together two algorithms, the combined running time is in O(max{f(n), g(n)}). There's always one that 'dominates' the runtime, making the affect of the other negligible.

1

The Answer is O(max{f(n), g(n)})

This is only correct if the programms run independently of each other. Anyhow, let's assume, this is the case.

In order to answer the why, we need to take a closer look at what the BIG-O-notation represents. Contrary to the way you stated it, it does not represent time but an upperbound on the complexity.

So while running both programms might take more time, the upperbound on the complexity won't increase.

Lets considder an example: P_1 calculates the the product of all pairs of n numbers in a vector, it is implemented using nested loops, and therefore has a complexity of O(n*n). P_2 just prints the numbers in a single loop and therefore has a complexity of O(n).

Now if we run both programms at the same time, the nested loops of P_1 are the most 'complex' part, leaving the combination with a complexity of O(n*n)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.