Problem Detail: What does $log^{O(1)}n$ mean? I am aware of big-O notation, but this notation makes no sense to me. I can’t find anything about it either, because there is no way a search engine interprets this correctly. For a bit of context, the sentence where I found it reads “[…] we call a function [efficient] if it uses $O(log n)$ space and at most time $log^{O(1)}n$ per item.”
Asked By : Oebele
Answered By : David Richerby
You need to ignore for a moment the strong feeling that the “$O$” is in the wrong place and plough on with the definition regardless. $f(n) = log^{O(1)}n$ means that there exist constants $k$ and $n_0$ such that, for all $ngeq n_0$, $f(n) leq log^{kcdot 1}n = log^k n$. Note that $log^k n$ means $(log n)^k$. Functions of the form $log^{O(1)}n$ are often called polylogarithmic and you might hear people say, “$f$ is polylog $n$.” You’ll notice that it’s easy to prove that $2n=O(n)$, since $2nleq k n$ for all $ngeq 0$, where $k=2$. You might be wondering if $2log n = log^{O(1)}n$. The answer is yes since, for large enough $n$, $log ngeq 2$, so $2log n leq log^2n$ for large enough $n$. On a related note, you’ll often see polynomials written as $n^{O(1)}$: same idea.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48527
