Time complexity

Question

Which one is larger $O(√n)$  or  $O(log n)$ ?

Answer 1

apply log both sides.... if result is asymptotically equal we can't say anything

if result is asymptotically not equal, then you can say.

given that f(n)=n$\frac{1}{2}$  and g(n) = log (n)

if you apply log on both sides...

$\frac{1}{2}$ log n , log log n ===> they are not asymptotically equal, therefore f(n) is larger than g(n)

 

ref : https://www.youtube.com/watch?v=AQ7Zao3bEfw&list=PLsFENPUZBqipuTJXgm7xAOR0UnY_8OY07&index=5&t=0s

Comments

if they asymptotically equal,

then you can solve by applying $\lim_{n\rightarrow ∞} \frac{f(n)}{g(n)} = result$

if result = 0 ===> f(n)=o(g(n))

if result ≤ c  ( where c>0 )===> f(n)=O(g(n))

if result = ∞ ===> f(n)=ω(g(n))

if result ≥ c  ( where c>0 )===> f(n)=Ω(g(n))

---

@Shaik Masthan. It would be helpful if you'll provide an example for each case as sometimes things fall in more than one cases and it is hard to see in first sight in which case this answer belongs acc. to the method you've given. (Please provide corner cases example as Kiran sir has provided during his explanation.)

---

@Shaik Masthan

if result ≤ c  ( where c>0 )===> f(n)=O(g(n))

Sir what to take as c so that 

if result ≤ c  ( where c>0 )===> f(n)=O(g(n)) and 
if result ≥ c  ( where c>0 )===> f(n)=Ω(g(n)) can be differentiated?

---

for some constant