From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$ is unsolvable using the Master Theorem, whereas $$T(n)= \begin{cases} T({n/2})+(\log(n))^{2}, & \text{if $n>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$ is solvable using the Master Theorem. Why is this?

EDIT: Why doesn't this floored example work? Isn't it monotonically increasing?

  • $\begingroup$ You can use the master theorem on your recurrence with floor. $\endgroup$ Oct 24, 2019 at 10:18