0
$\begingroup$

I have a problem that is has the notation $lg^2 n$ and I just want to verify that it actually means / is the same as $(lg n)^2$

If it is not the same please tell me how to evaluate $lg^2 n$ (always assuming lg is base 2).

I do not have a source to quote from, I was just given a bunch of algorithms to sort out. Sorting them isn't a problem for me as long as I know what they are saying :) I retyped the notation exactly how it looks and provided it in the picture below. I have included some other formulas too so you can compare the notations. I imagine it was written as $lg^2 n$ just so he didn't have to use parenthesis, but I wanted to verify.

enter image description here

  • 0
    @Arturo Magidin I thought that too, but I wanted to be sure :)2011-02-27

1 Answers 1

3

It depends on the source. Usually, the notation $f^n(x)$ to mean "$(f(x))^n$" is restricted to trigonometric and hyperbolic functions, and for other functions $f^n(x)$ means $\underbrace{f\circ\dots\circ f}_{\mbox{$n$ times}}(x).$

So you need to know what convention your source is using. It could mean either $\mathrm{lg}(\mathrm{lg}(n))$, following the usual conventions, or $(\mathrm{lg}(n))^2$, if the author is using the notation as in the case of trigonometric functions.

  • 0
    I asked around and in my particular case it means `(lg n)^2)`2011-02-27