Logarithms

Some basic notation:

• lg x is the base 2 logarithm of x (can also be written log2x)
• ln x is the base e natural logarithm of x (can also be written logex)
• lgnx is the notation for (lg x)n

Useful identities:

• x = ylogyx
• logx(yz) = logxy + logxz
• logxyz = z logxy
• logxy = logzy/logzx
• logx1/y = -logxy
• logxy = 1/logyx
• xlogyz = zlogyx

We say that a function f is polyalgorithmically bound if f(x) = lgO(1)x. Since logxz = k logyz for some k, we usually use base 2 for the big O notation, i.e.

	  O(logxz) = O(logyz) = O(lg z).
	

Note that any polynomial function grows faster than any polyalgorithmic function.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.