We know that log(n) = O(sqrt n ) I am wondering if is it valid to say that log(n) is theta( sqrt n ) . numerically , i proved that it is right ; yet i am not too sure about it . Would like some help
log n is NOT in Theta(sqrt n), since sqrt n is asymptotically greater than log n, meaning that log n isn't in Omega(sqrt n). In other words, sqrt n cannot be an asymptotic lower bound for log n.
Refer to this definition of big theta. Substitute sqrt n for g(n) and log n for f(n) in the definition and you will see that you can easily find a k2 and n0 such that the definition is satisfied (which is why log n is in O(sqrt n)), while finding a suitable k1 will prove impossible (which is why log n is NOT in Omega(sqrt n)).