[Algo] complexity

Question

f(n) + o(f(n)) = thetha(f(n))

Does this hold? o is small -oh notation.

Comments

Nopes ! small oh is strictly increasing and will never be equal to function itself.

---

If my f(n) is n^3 .

f(n) + o(f(n)) = n^3 + something whose small o is n^3.Means that something must be less than n^3.

so it should be n^3+something less than n^3 = thetha n^3.

Just a rough thing that i am thinking

---

Yes ! i misinterpreted the small o with small omega! you are correct.

Answer 1

o(f(n)) suggests that some function  g(n)  which is strictly smaller than f(n)..

Hence in f(n) + o(g(n)) , we need to see the dominating term which is f(n) here as g(n) is stricty less than f(n)..

We know

f(n)  = Theta(f(n)) 

As f(n) + o(f(n)) will result to f(n) only ..Hence 

f(n)  + o(f(n))  =   Theta(f(n))

Answer 2

True

$f(n)+o(f(n))=\Theta (f(n))$

let $g(n)=o(f(n))$$\Rightarrow c*f(n)> g(n)......................(1)$

We can write the Above question as-:

$f(n)+g(n)=\Theta (f(n))$

Now ,from $(1)$

we have ,

$f(n)>g(n)\Rightarrow f(n)+f(n)>g(n)+f(n)\Rightarrow f(n)+g(n)= O(f(n))$

$\Rightarrow f(n)+o(f(n))=O(f(n)).........................(2)$

---

$f(n)+g(n)=\Theta (f(n))$

$\Rightarrow f(n)+g(n)>f(n)\Rightarrow f(n)+g(n)=\Omega (f(n))$

$\Rightarrow f(n)+o(f(n))=\Omega (f(n)).....................(3)$

from$(2)$ & $(3)$,

$f(n)+o(f(n))=\Theta (f(n))$