Are the notations $lg^2 n$ and $(lg n)^2$ the same thing?

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

$\endgroup$ 4

1 Answer

$\begingroup$

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.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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