# Big-O complexity of sqrt(n) [duplicate]

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}$?

• OK, there are a lot of misconceptions here. First off, we need to distinguish between functions and problems. A function is a mathematical relationship between numbers, such as $\log$ or $\sqrt{\phantom{x}}$. A problem is a thing requiring a computational solution. Functions do not have complexity: functions are used to measure the complexity of problems. Analogy: the height of the Empire State Building is 443m but the number 443 doesn't have a height; it's something we use to measure heights. Functions don't have complexity so they aren't in complexity classes. Sep 6, 2016 at 8:50
• From the way you write, you seem to be under the misapprehension that there is some "official" list of functions $f$ such that you're allowed to write $O(f)$, and your job is to find out which one of these functions applies to square root. This is absolutely not the case. Informally, $g=O(f)$ means $g$ is kinda-less-than $f$, and it behaves much like $<$. You wouldn't ask "What's the number $x$ such that I can write $\pi<x$?" but your question about $\sqrt{n}$ is essentially the same thing. Well, $\sqrt{n}$ is kinda-less-than $n^2$ and $2^n$ and $n\log n$ and infinitely many other functions. Sep 6, 2016 at 9:00
• I'm sure I'm getting the terms wrong, and appreciate the effort you put into commenting, @DavidRicherby. For reference, here's the problem set I'm working on: ocw.mit.edu/courses/electrical-engineering-and-computer-science/… I'm not sure what value to glean from the function/problem terminology clarification. I think one can, in fact, describe any function in terms of an upper bounds of complexity using Big-O notation. Is that wrong? It's literally (as in phrasing) what the problem set is asking me to do. Sep 6, 2016 at 19:07
• That's a disappointingly loose use of terminology by the question setters. :-( They're asking you to sort the [mathematical] functions by order of growth (which is what they're calling "complexity"): for each of the sets of functions, you need to sort them so that each one is big-O of the next. And, yes, you can use any function at all on either side of a big-O bound: you understood that correctly and I probably thought you'd misunderstood it because you tailored your question to the exercise you're trying to solve. Sep 6, 2016 at 19:27

$\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})$.

• I forgot the equivalence between square root and power of 0.5. This was the missing piece for me and it all came together after that. Thank you. Sep 5, 2016 at 21:03