How to add/merge several Big O's into one

Question

If I have an algorithm which is comprised of (let's say) three sub-algorithms, all with different O() characteristics, e.g.:

• algorithm A: O(n)
• algorithm B: O(log(n))
• algorithm C: O(n log(n))

How do I theoretically estimate the O() for the entire algorithm? I.e. not clocking it or performing any other practical measurement.

Is there a well known formula or procedure?

Answer 1

Is there a well known formula or procedure?

Since that’s basic maths, yes. But it’s even simpler in your case: since all of these give an upper bound, you can simply take the maximum of all the bounds to get the total upper bound.

– Provided that all of these algorithms are chained (rather than nested). If the algorithms are nested, you need to multiply their upper bounds (in the simplest case).

To illustrate, let’s say that you have a container data structure which has a cost of O(log n) for lookup of a single element. You also have an algorithm that needs such a lookup, but has running time O(n) itself, assuming constant costs for lookup, and using a single loop over the input, with a constant number of lookups per loop.

Now, if you want to use the previously mentioned container data structure with this algorithm, its lookup runtime obviously replaces the (assumed) constant-time lookup. So we’ve got the same loop, but each of its iterations now takes O(log n) instead of constant-time O(1), so the overall runtime becomes O(n log n).

Answer 2

The "total" complexity is the worst case of all sub algorithms. In your example: O(n*log(n))

Definition of O(f(n)) is that starting from some number (some n0), there is a constant, 'Const', where the total number of actions on input of size n is less than Const*f(n).

Therefore, if you have group of sub algorithms, the complexity will always be less then Sigma of all consts (Const1 + Const2 + ...) multiplied by the worst complexity function (e.g., from "n", "n*logn" and "n^2" it'll be n^2). By complexity definition it's the worst complexity in the group.

Example:

1. Let's assume we're sorting an array (n*logn)
2. Finding the item with key higher then x (logn)

Assume Const1 of the sort is 5 (meaning we can sort list of n items in less than 5*n*logn actions) and the Const2 is 3 (meaning we can find the element in less than 3*logn actions).

In this case, it's clear that the total number of action of both algorithms is less than (5+3)*n*logn actions, and therefore it O(n*logn)