In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation:

  • $\log^2(n) = ?$

  • $\log(n)^2 = ?$

  • $(\log n)^2 = (\log(n)) \times (\log(n))$

  • $\log(n^2) = \log(n \times n)$

  • $\log \log n = \log(\log(n))$

The last three case are easy enough to understand, but what about the first two? The operator precedence is unclear. Do they mean $\log(n \times n)$, or do they mean $(\log(n)) \times (\log(n))$, or do they mean $\log(\log(n))$?

Citing a reliable source would be a plus, so that I can confidently add this information to Wikipedia.

Note I'm asking about the meaning of big-O or about $O(\log n)$ complexity. I'm interested in what the $^2$ means (square the $n$, square the result of $\log(n)$, or $\log^2$ = $\log \cdot \log$).

  • $\begingroup$ Log^2 (n) means that it's proportional to the log of the log for a problem of size n. Log(n)^2 means that it's proportional to the square of the log. $\endgroup$
    – ConcernedOfTunbridgeWells
    Jan 8, 2016 at 12:04
  • 4
    $\begingroup$ Re ConcernedOfTunbridgeWells, no. $\log^2n$ means $(\log n)^2$, in just the same way that, in the trigonometric identities you learnt in school, $\sin^2 x$ means $(\sin x)^2$ and not $\sin(\sin x)$. $\endgroup$ Jan 14, 2016 at 2:45
  • 1
    $\begingroup$ @DavidRicherby The authors of "Concrete Mathematics" have commented on this notation issues. See Section 9.3 or the paragraph excerpted from that book in my answer below. $\endgroup$
    – hengxin
    Jan 14, 2016 at 6:10
  • $\begingroup$ Community votes, please: is this ontopic? It seems to be a pure mathematics question about notation. $\endgroup$
    – Raphael
    Jan 14, 2016 at 8:03
  • $\begingroup$ @Raphael from what I've seen, there seems to be different conventions in different CS communities, some use $\log^2 n = (\log n)^2$, and some (like operations research, apparently) use $\log^2 n = \log(\log n)$, just like $\sin^-1$ is the inverse of $\sin$, not $\frac{1}{\sin}$. Hence my question is specific to CS, since even within our community, people in different subfields don't necessarily agree. $\endgroup$ Jan 15, 2016 at 9:41

5 Answers 5


Regarding the operator precedence, as specified the other answers:

log²(n) : possibly ambiguous
              most commonly 'log(n) * log(n) '
              but possible that some writers intend 'log(log(n))'

log(n)² : ambiguous, log(n) * log(n) or 2log(n) 

Now, you asked about their meaning in the context of asymptotic behaviour and, specifically, Big-O notation. Below follows a note regarding seeing research articles state that the time complexity of an algorithm is log(n²), which is, in the context of Big-O notation, somewhat of a misuse of the notation.

First note that

 log(n²) = 2log (n)

If some some arbitrary function f(n) is in O(log(n²)) = O(2log(n), then we can show that f(n) is in O(log(n).

From the definition of O(n), we can state the following

f(n) is in O(g(n))

=> |f(n)| ≤ k*|g(n)|, for some constant k>0                 (+)
                      for n sufficiently large (say, n>N)

See e.g. this reference covering Big-O notation.

Now, if f(n) is in O(2log(n), then there exists some set of positive constants k and N such that the following holds

    |f(n)| ≤ k*|log(n)|, for n>N                               

<=> |f(n)| ≤ k/2*|2log(n)|, for n>N                          (++)

Hence, we can just choose a constant k2=k/2 and it follows from (++) that f(n) is in O(log(n).

Key point: The purpose of this explanation is that never should you see an article describe the asymptotic behaviour of an algorithm as O(log(n²)), as this is a redundant way of saying that the algorithm is in O(log(n)).

For explanations regarding what different O(log(n) variations means with regard to the algorithms behaviour, see e.g. the links provided by other answers, as well as the numerous threads on SO covering these subject (e.g. time complexity of binary search, and so on).

  • 4
    $\begingroup$ An author would have to be awfully obtuse to write $\log(n)^2$ and mean $2\log n$ by it... $\endgroup$
    – D.W.
    Jan 14, 2016 at 6:33

For the first one, you can find an answer here:

(log(n))² means log²(n)

And from this question for example you can guess that:

log(n)² = (log(n))²

So both the first and the second essentially mean

(log(n)) × (log(n))

(Unfortunately, not with more reliable sources than stackexchange...)

  • 8
    $\begingroup$ (log(n))² means log²(n) Not always. It is often log(log(n)), depending on context. (I have seen in the past used at this notation more than once. I personally don't like it, but some people do). $\endgroup$
    – amit
    Jan 8, 2016 at 12:23
  • $\begingroup$ The question you referred used $(\log n)^2)$ not $\log (n)^2$ $\endgroup$
    – padawan
    Jan 14, 2016 at 20:40

$\log^kn = \log^k(n) = \left(\log(n)\right)^k = \underbrace{\log (n)* \log (n) * \dots * \log (n)}_{\text{k times}}$

$\log n^k = \log (n^k) = \log (\underbrace{n * n * \dots * n}_{\text{k times}})$

I think $\log (n)^k$ is a bad notation, since $\log(\cdot)$ is a function and brackets must be used in order to resolve ambiguity. However, my intuitions say that

$\log (n)^k = \left(\log(n)\right)^k$

Additionally, I suggest this video.


log²(n) = log(n) * log(n)

log(n)² is indeed ambiguous, it could mean either log[(n)²](i.e. 2log(n)) or [log(n)]² (i.e. log(n) * log(n)).


The following is the opinion of the authors of "Concrete Mathematics" (Section 9.3 "$O$ Manipulation"; formatting added by myself):

Equation (9.27) (i.e. $O(f(n) g(n)) = f(n) O(g(n))$) and (9.23) (i.e. $f(n) = O(f(n))$) allow us to derive the identity $O(f(n)^2) = O(f(n))^2$. This sometimes helps avoid parentheses, since we can write $O(\log n)^2$ instead of $O((\log n)^2)$. Both of these are preferable to $O(\log^2 n)$, which is ambiguous because some authors use it to mean $O(\log \log n)$.

Can we also write $O(\log n)^{-1}$ instead of $O((\log n)^{-1})$?

No! This is an abuse of notation, since the set of functions $1/O(\log n)$ is neither a subset nor a superset of $O(1/\log n)$. We could legitimately substitue $\Omega(\log n)^{-1}$ for $O((\log n)^{-1})$, but this would be awkward. So we'll restrict our use of "exponents outside of the $O$" to constant, positive integer exponents.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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