3
$\begingroup$

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

$\endgroup$

migrated from stackoverflow.com Jan 14 '16 at 1:20

This question came from our site for professional and enthusiast programmers.

  • $\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 '16 at 12:04
  • 2
    $\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$ – David Richerby Jan 14 '16 at 2:45
  • $\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 '16 at 6:10
  • $\begingroup$ Community votes, please: is this ontopic? It seems to be a pure mathematics question about notation. $\endgroup$ – Raphael Jan 14 '16 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$ – Georges Dupéron Jan 15 '16 at 9:41
4
$\begingroup$

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...)

$\endgroup$
  • 5
    $\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 '16 at 12:23
  • $\begingroup$ The question you referred used $(\log n)^2)$ not $\log (n)^2$ $\endgroup$ – padawan Jan 14 '16 at 20:40
3
$\begingroup$

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).

$\endgroup$
  • 2
    $\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 '16 at 6:33
2
$\begingroup$

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)).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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