And that's just 1 plus log base b of n,

because that's the number of terms in our summation times O(n to the d).

Well the 1 is a low order term we don't care about, and log base b of n can

just be treated as log n, because a base change is just some multiplicative factor,

and that disappears in our big O notation.

So we end up with, as we see in the theorem, O(n to the d times log n).

And then our final case, is d is less than log base b of a,

which is equivalent to saying a over b to the d is greater than 1.

So here, our multiplicative factor is greater than 1.

So our smallest term is the first term and our largest term is the last term.

So in this case, this is big O of our

last term is O(n to the d) times a over b to the d to the log b of n.

So, i is log base b of n.

This is a bit of a mess.

Let's see whether we can fix this a little bit.

So let's go ahead and apply the log base b of n power separately to a and b to the d.

So we have, in the numerator, a to the log base b of n.

And then the denominator, b to the d times log base b of n.

Well, b to the log base b of n is just n.

So, that's going to disappear down to n to the d in the denominator.

In the numerator, a to the log base b of n,

by logarithmic identity is equal to n to the log base b of a.

So we can swap those other two.