4
$\begingroup$

In this paper they mention an algorithm has big-O time complexity of $O(\log^4n)$, what does the $\log^4$ mean? I understand $\log_4x$ is the log with base 4 of x.

$\endgroup$
4
  • 2
    $\begingroup$ $\log$ to the power of $4$ in this case. $\endgroup$
    – Thomas
    Oct 8, 2015 at 19:46
  • 2
    $\begingroup$ @Thomas so $(log(n))^4$ right? $\endgroup$
    – AJP
    Oct 8, 2015 at 20:10
  • 1
    $\begingroup$ yes, that's correct $\endgroup$
    – Thomas
    Oct 8, 2015 at 20:13
  • $\begingroup$ This is a horrific notation, jesus. $\endgroup$
    – iono
    Feb 11, 2023 at 13:12

1 Answer 1

3
$\begingroup$

As mentioned by another user already this must be an exponent. The only exception where a superscript would be used for a logarithm to denote the base is as follows: $^4 log(n)$, which means log base 4.

$\endgroup$
6
  • $\begingroup$ Good. I'm glad there seems to be consensus on this even though it is unusual notation. $\endgroup$
    – AJP
    Oct 8, 2015 at 20:09
  • $\begingroup$ @AJP That notation is quite usual in Europe... $\endgroup$
    – imranfat
    Oct 8, 2015 at 20:15
  • $\begingroup$ @imranfat I've seen the $^4log(n)$ before though but never the $log^4(n)$... $\endgroup$
    – AJP
    Oct 8, 2015 at 20:19
  • 1
    $\begingroup$ @AJP: I've seen $\log^4(n)$ before but never $^4\log(n)$. (I live in Europe.) $\endgroup$
    – TonyK
    Oct 8, 2015 at 20:23
  • 1
    $\begingroup$ My first guess was that it meant $\log (\log (\log (\log n))))$. I'm glad it's not. The instance I saw was $\log^r(n)$. I didn't want to have to think about an arbitrary number of iterations of $\log$ of $\log$. $\endgroup$
    – Mars
    Feb 14, 2021 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .