# Solving Recursive Equations: How to transform the domain in such cases?

I understand that a widely-used recursive equation for the Binary Search is as follows: \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n}{2}) + 1, \quad n>1 \end{align}

In order to solve the recursive equation we would simply transform the domain by setting $n = 2^k$, write the transformed equation, go through the telescoping and all that good stuff...

Anyway, my professor said that sometimes there may be an odd number of elements in a sorted list, in which case the equation would look like: \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n-1}{2}) + 1,\quad n>1 \end{align}

Then I wondered, how would I perform a domain transformation on such an equation?

Thank you very much!

-
Presumably by $T(n-1/2)$ you mean $T((n-1)/2)$. Please use proper parentheses as what you wrote is $T(n-(1/2))$. Even better, as it is easier to read, $T(\frac {n-1}2)$ For $\LaTeX$ you can see this – Ross Millikan Mar 18 '13 at 16:12