Problem Detail: I’m trying to backfill missing CS knowledge and going through the MIT 6.006 course. It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather than just guessing. The question is to reduce this to big-O notation, then rank it: $$f(n) = n cdot sqrt{n}$$ I see in this answer that $sqrt{n} gt log{n}$ I don’t understand how to think about the complexity of $sqrt{n}$. What is the complexity class of $sqrt{n}$? What is the relationship between $sqrt{n}$ and $log{n}$?
Asked By : SimplGy
Answered By : Mario Cervera
$sqrt{n}$ belongs to the class of sublinear polynomials since $sqrt{n}=n^{1/2}$. From Wikipedia (beware of the difference between Little-o and Big-O notations):
An algorithm is said to run in sublinear time if $T(n) = o(n)$
Note that constant factors do matter when they are part of the exponent; therefore, we can consider $O(n^{1/2})$ to be different from (and less than) $O(n)$. With respect to the relationship between $log(n)$ and $sqrt{n}$, you can find here a discussion about why $log(n) = O(sqrt{n})$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63181
