Timeline for Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\log_b a+\epsilon})$
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17, 2020 at 20:57 | history | edited | jsbc | CC BY-SA 4.0 |
Adding the important note.
|
| Sep 17, 2020 at 20:17 | comment | added | Yuval Filmus | If all you know is that $f(n) = \Omega(n^{\log_ba+\epsilon})$, you cannot conclude that $f$ is regular. For example, suppose that $a=b=2$, and consider $f(n) = 16^{\lfloor \log_4n \rfloor} = \Omega(n^2)$. If $n=2\cdot 4^m$ for integer $m$ then $2f(n/2) = 2f(n)$, and in particular there is no $c<1$ such that for all large enough $n$, we have $2f(n/2)\leq cf(n)$. | |
| Sep 17, 2020 at 14:08 | history | edited | jsbc | CC BY-SA 4.0 |
added 5 characters in body
|
| Sep 17, 2020 at 13:47 | history | answered | jsbc | CC BY-SA 4.0 |