2 votes 2 votes Can someone please prove or disprove the following conjecture? 1. Let f(n) be a asymptotically positive function. $f(n) + o(f(n)) = \Theta(f(n))$ Note that this is small-oh. Algorithms algorithms asymptotic-notation time-complexity + – Manu Thakur asked Dec 20, 2017 Manu Thakur 741 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply joshi_nitish commented Dec 21, 2017 reply Follow Share $f(n)+o(f(n))=\Theta (f(n))$ multiplying by some constant, throughout, $k.f(n)+o(k.f(n))=\Theta (k.f(n))$ taking LHS, $let$, $g(n)=o(f(n))$ $\Rightarrow$ $g(n)<k.f(n)$ //according to definition of small-oh LHS $\equiv$ $k.f(n)+g(n)$ //now since g(n) is always less than f(n), therefore f(n) is dominating(greatest) term here. and dominating(greatest) term of a positive expression is always its $\Theta$ $\therefore$ $k.f(n)+g(n)$ $= \Theta (k.f(n))$ $\Rightarrow$ $f(n)+o(f(n))=\Theta (f(n))$ above conjecture is true 4 votes 4 votes Anu007 commented Dec 21, 2017 reply Follow Share need to make it answer 0 votes 0 votes Manu Thakur commented Dec 21, 2017 reply Follow Share yes Nitish, g(n) will always be less than f(n) and max(f(n),g(n)) =f(n) Hence, theeta(f(n)) 0 votes 0 votes Mahbub Alam commented Nov 19, 2018 reply Follow Share good explanation 0 votes 0 votes Please log in or register to add a comment.