Big O notation (on both sides)

Question

I need step-by-step prove that: 7 + O(n) = O(n)

I have no idea how to do it when there are Big O on both sides.

I think I understand concept of big O notation but why is there Big O on both sides?

Answer 1

O(n)+constant = O(n) constant doesn't make much difference in this scenario so we can omit constant.

Answer 2

Here is the formal definition of big O notation:

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. (big-O notation).

If your complexity is, for example, O(n^2), then you can guarantee that there is some value of n (greater than k) after which f(n) in no case will exceed c g(n).

Let's try to prove q(n) = f(n) + 7 is O(n), where f(n) is O(n):

1. From the definition, there exists a function f(n) such that f(n) ≤ c n for all n ≥ k.

2. Now, we want to prove q(n) is O(n). We prove this by contradiction. We say if q(n) is not O(n), there exist no k' and c' such that q(n) ≤ c' n for all n ≥ k' (original assumption). Now,

q(n) = f(n) + 7 ≤ c n + 7 for all n ≥ k ---- (1).

From the definition, c > 0 and k > 0. Now, (c + 1) n ≥ c n + 7 for all n ≥ max(k, 7), c > 0

=> (c + 1) n ≥ f(n) + 7 for all n ≥ max(k, 7), c > 0 (From eqn (1))

=> (c + 1) n ≥ q(n) for all n ≥ max(k, 7), c > 0 ----(2)

Substituting c' = c + 1 and k' = max(k, 7) in the above equation, we quickly find a contradiction:

c' n ≥ q(n) for all n ≥ k' (written as original assumption in step 2)

This is a contradiction in that our original assumption that no such values of c' and k' exist is violated. Hence, O(n) + 7 is O(n).

This completes your proof. Hope it helps!

EDIT: It is also sufficient to show that some k' and c' exist for our proof to work. We could simply skip the contradiction part.

Answer 3

This use of notation does not accord with the formal definition of big O notation, so it's not clear what level of formality the proof needs to be. Also, since the notation is not formal, it takes some interpretation to decide what actually needs to be proved.

I interpret this as asking for a proof that, given any function which is in O(n), if you add 7 to all of the values of that function, then the new function is also in O(n). More formally, for all f in O(n), the function g(n) = f(n) + 7 is also in O(n).

This can be proved straightforwardly from the definition:

1. We need to show that, for every f in O(n), the function g(n) = f(n) + 7 is also in O(n).
2. Since f is in O(n), there exist constants c and N such that for all n >= N, the value of f(n) <= cN.
3. It follows that g(n) = f(n) + 7 <= cN + 7 <= (c + 7)N for all n >= N, so long as N >= 1.

So given constants c and N proving f is in O(n), the constants (c + 7) and max(N, 1) work for proving that g is in O(n). QED.

Answer 4

The statement 7 + O(n) = O(n) does not make much sense. O : (ℕ → ℕ) → P(ℕ → ℕ) is a function that maps a function to a set of functions. You can not add seven to a set of functions. You could "include" it, but this is likely not what the expression aims to do.

What you likely need to do is proof that O(n+7) = O(n). You can proof that two sets are equal by proving that each element in the first set is a member of the second set, and each element in the second set is a member of the first set.

The set of functions that arises from O(n) is defined as each function g, such that for this g there exists an n₀ and a value k > 0, such that for all n∈ℕ with n > n₀, it holds that g(n)≤k×n. You thus need to proof that all these functions are a member of the set that arises from O(n+7), and vice versa.

Answer 5

Big O notation is applicable for asymptotically large value of n. Therefore constants make no change to the Big O notations.