0
$\begingroup$

$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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Apr 2, 2013 at 13:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .