• We’ve encountered some of the most common complexities: O(n), O(1), O(n^2)
• Sometimes big O expressions involve more complex mathematical expressions
• One that appears more often than you might like the logarithm !

Wait, what’s a log again?

logarithm is the inverse of exponantiation

log v 2(8) = 3 ——> 2^3 = 8

log v2 (value) = exponent ———> 2 ^ exponent = value

we’ll omit the 2

log === log /subscript 2

Rule of thumb

• This isn’t a math course, so here’s a rule of thumb
• The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that’s less than or equal to one.

8

/2

4

/2

2

/2