Using Recurrence:

$a^n = a^{\frac{n}{2}}.a^{\frac{n}{2}}$

(here n is in a power of 2, so we would never have a fraction, each time when we divide n with 2.)

Here once we solve $a^{\frac{n}{2}}$, then we need one more multiplication that is multiplying $a^{\frac{n}{2}}$ to itself.

Hence recurrence:

T(n) = T$(\frac{n}{2})$+1.

Option 1 satisfies this.

$a^n = a^{\frac{n}{2}}.a^{\frac{n}{2}}$

(here n is in a power of 2, so we would never have a fraction, each time when we divide n with 2.)

Here once we solve $a^{\frac{n}{2}}$, then we need one more multiplication that is multiplying $a^{\frac{n}{2}}$ to itself.

Hence recurrence:

T(n) = T$(\frac{n}{2})$+1.

Option 1 satisfies this.