5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Sep 6 '16 at 8:50
  • $\begingroup$ 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. $\endgroup$ – David Richerby Sep 6 '16 at 9:00
  • $\begingroup$ 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. $\endgroup$ – SimplGy Sep 6 '16 at 19:07
  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 6 '16 at 19:27
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – SimplGy Sep 5 '16 at 21:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.