CODEWITHSUNDEEP
algorithmbig-o
OldSchool
OldSchool

Reputation: 2183

Why Induction always does not work with Big-O?

I am currently watching ocw video courses on Algorithms and in second lecture i stuck at a point where professor proves the following statement by induction:-

n=O(1)

proof:-    

For base case    
1=O(1)    
suppose n-1 = O(1)    
=> 1+(n-1)=O(1)+O(1)     
=> n=O(1).    
hence it is proved.

But the professor told that we cannot induct over Big-O and the above proof is not true but why?

Upvotes: 3

Views: 864

Answers (3)

AbcAeffchen
AbcAeffchen

Reputation: 15017

Basically in math induction is a tool, to get from a well known position a well controllable step further. This don't have to be a step like n → n+1 or n → 2⋅n, but most likely it is. In most cases the problem will be, that the well controllable step is of constant size, so in Big-O it just get lost.

But in some cases you can use the Big-O just for simplification while calculating the complexity, like

(n+a+1)(n-2⋅b)(n2-3) = n4+O(n3)                (for constants a and b)

There are also cases, where you can see the complexity in the induction step.

Example:
Find the complexity of f(n) = f(n-1) + f(n-2) with n ≥ 2 and f(0) = f(1) = 1.
The step n → n+1 yields 

2⋅f(n-1) ≤ f(n+1) ≤ 2⋅f(n)

so basically the size doubles for a +1. you need n +1's to sum up to n, that yields the first value doubles about n times. The beginning (f(1)) is in O(1) so 2n ⋅ O(1) is in O(2n).

Finally there are cases in which you can proof the complexity by induction.

Example:
Find the complexity of n!.
Proof: 1 is in O(1). Suppose (n-1)! is in O(1). Then 

n! = n⋅(n-1)! = n * O(1) = O(n).

Damn, n! can't be in O(1) because (n+1)! had to be also in O(1), but it isn't. Next try:
Suppose (n-1)! is in O(nk). 

n! = n⋅(n-1)! = n ⋅ O(nk) = O(nk+1)

Damn, failed again. If n! is in O(nk), (n+1)! is supposed to be in 

O((n+1)k) = O(nk + k⋅nk-1 + ...[smaller monomials]) = O(nk)

But for k = n this would work, since for n! in O(nn), (n+1)! is supposed to be in O((n+1)n+1) and in fact, n! is in O(nn), but it is not a tight upper bound. To proof a better complexity you have to use better methods than induction.

So this is more an example to disproof a complexity by using induction.

In general I would not say, that there is no complexity that can be proven by induction, but in most cases exits better ways to proof it.

Upvotes: 0

Corei13
Corei13

Reputation: 261

You can induct over Big-O, but the given induction process is not correct when n is a variable instead of a constant.

When you write 1 = O(1), the interpretation would be

if f_1(n) = 1 for all n then f_1(n) = O(1)

which is correct.

Now if we define f_a(n) = a for all n, then by induction we can prove that f_a(n) = O(1) for all a, which is also correct.

But if n is not a constant but a variable you can't get n = O(1) as a result of your induction since there is no k such that f_k(n) = n for all n.

Upvotes: 4

Joni
Joni

Reputation: 111349

Mathematical induction is a tool to prove statements parametrized by integers. It cannot be applied in this case because the statement you are studying changes half way through: you take a constant 1 as the base case, and then assume a statement about the function f(n)=n-1.

The proof is correct in showing that any constant n is in O(1), though.

Upvotes: 3

Related Questions