0

$lg\lceil \frac{n}{2} \rceil + 1$

How do I get rid of the ceiling? In order to lose the ceiling I add +1 and get the following expression which I don't know how to simplify $lg (\frac{n +1} {2}) + 1$. How do I proceed from here? I want to calculate $lg (\frac{n}{2}) + 1$.

Thanks for your time

Peter
  • 111

1 Answers1

1

Basically, you can't. $\lg \lceil \frac{n}{2} \rceil + 1$ is different from other expressions. This shows up many times in asymptotic analysis of algorithms, where you may be able to say you don't care between $n$ and $n+1$ because $n$ is large compared to $1$ and just ignore the ceiling. Sometimes you round $n$ up to the next power of $2$ so you can keep dividing by $2$ all the way down, then argue for smaller $n$ the function is smaller.

Ross Millikan
  • 374,822
  • Yes I know ross. However, our professor insists that we do not omit the floors and ceilings and that really complicates my life! Even the authors of the book note what you said. – Peter Apr 02 '13 at 13:24