Reputation: 3733

Big O Notation: The sum of function body

If a function body invokes 3 different functions, all of the order O(n), how do I calculate the order of the outer (containing) function? Yes, this is homework, and I've surprisingly failed to find a relevant example in the textbook, nor the slides of our recent lectures.

private void bigFunction(){
    smallFunction1();   // O(n)
    smallFunction2();   // O(n)
    smallFunction3();   // O(n)
} // Now what does this result in?

My initial thought is O(n), but I want to be certain.

Upvotes: 2

Answers (4)

Patricia Shanahan

Reputation: 26185

The best way of being really sure of something like this is to construct a proof based on the definition, quoted in @Jon's answer:

A function f(x) is said to be O(g(n)) if there are numbers 
K and T such that for all x > T, f(x) < K * g(x).

Let f_1(n) be the time for smallFunction1(), f_2(n) for smallFunction2(), and f_3(n) for smallFunction3(), all in a size n problem.

Because f_1(n) is O(n), there exist K_1 and T_1 such that, for all n > T_1, f_1(n) < K_1 * n. Similarly, there exists K_2, T_2, K_3, and T_3 such that, for all n > T_2, f_2(n) < K_2 * n and for all n > T_3, f_3(n) < K_3 * n.

Let K equal K_1 + K_2 + K_3 and let T equal max(T_1, T_2, T_3). Then for all n > T, f_1(n) < K_1 * n, f_2(n) < K_2 * n, f_3(n) < K_3 * n.

The time to run the three functions consecutively, f_1(n) + f_2(n) + f_3(n), is less than K_1 * n + K_2 * n + K_3 * n = (K_1 + K_2 + K_3) * n = K * n, so the total time is O(n).

Upvotes: 0

Jon

Reputation: 437534

You need to keep in mind the definition of big-oh:

A function f(x) is said to be O(g(n)) if there are numbers K and T (which you can of course choose freely) such that for all x > T, f(x) < K * g(x).

Of particular importance is the fact that you are free to select any K that fits the bill, not just the smallest K that does. It is this property that leads to g(n) always being shown as not having any constant factors: the following two scenarios are completely equivalent:

f(x) = x, g(n) = 2n, K = 1
f(x) = x, g(n) = 4n, K = 1/2

Since you can make g have any constant factor you like simply by selecting K appropriately, in practice we do not bother and always treat g as always having no constant factor.

At this point it should be clear that O(g(n)) + O(g(n)) is still O(g(n)), because for the sum you can simply choose "double the usual" value for K and still have the same form for g(n). Therefore the sum of any constant number of O(n) functions is still O(n).

Upvotes: 0