2
$\begingroup$

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?

$\endgroup$

marked as duplicate by D.W. algorithms Oct 21 at 3:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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