DSC 20 Lecture 14

Logs

Proof ${\log }_a{b}^c=c\cdot {\log }_{a}b$

Proof ${\log }_{a}b=\frac{{\log }_{c}b}{{\log }_{c}a}$

Example ${\log }_{3}81=\frac{{\log }_{9}81}{{\log }_{9}3}=\frac{2}{1/2}=4$

Why we don't care about the base of logs in Big O notation

We can drop any constant terms because in Big O notation, we don’t care about them.

Properties of Orders of Growth

• Constants: Constant terms do not affect the order of growth of a process
• Logarithms: The base of a logarithm does not affect the order growth of a process
• Lower-order terms: The fastest-growing part of the computation dominates the total

Comparing Orders of Growth (n is the problem size)

Constant. The problem size doesn’t matter
Logarithmic growth.

Square root growth.
Linear growth.
Quadratic growth.
Exponential growth. Recursive fib takes steps, where

Abused Notation

VERY often Big-O is used in Big-Theta (in Computer Science)
Not as an upper bound!

Useful Formula, in the context of Big O