Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.