Calculating time complexity for CEOI 2018 — Toys (Day 2)
Разница между en1 и en2, 289 символ(ов) изменены
I am trying to estimate the upper bound of the time-complexity of [this solution](https://csacademy.com/submission/1717684/) by [user:ksun48,2018-08-17]. Currently, I am assuming the upper bound on the number of divisors of $N$ to be $\mathcal{O}(N^{1/3})$ based on [this codeforces blog](https://codeforces.me/blog/entry/14463). For simplicity, if we assume the bound on no. of divisors to be exactly $N^{1/3}$, the upper bound can be calculated as $N^{1/3} + N^{1/9} + N^{1/27} + ...$.↵

How can we find a tighter upper bound for this solution? ↵
, but that fact doesn't simplify the calculation of time complexity here.↵

- Is there a simple way to estimate a good upper bound for this solution?↵
- Is there some literature around formally calculating time complexity in such scenarios?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский xennygrimmato 2018-08-17 09:41:09 289 Remove incorrect time-complexity calculation
en1 Английский xennygrimmato 2018-08-17 09:33:24 607 Initial revision (published)