```cpp↵
unordered_map<uint64_t, uint64_t> ump;↵
uint64_t solve(uint64_t n) {↵
if (ump.count(n))↵
return ump[n];↵
uint64_t p = cube(n - 1);↵
uint64_t c = p * p * p;↵
uint64_t res = solve(c) + solve(n - c) + (n - c);↵
ump[n] = res;↵
return res;↵
}↵
```↵
↵
I'm curious about the time complexity of this recursive function.↵
↵
Here, the function `cube` is used to calculate the **cube root** (not the cube). You can assume that it's $O(1)$ or $O(\log n)$.↵
↵
I believe it is $\Omega(\sqrt[3]{n})$, but I'd like to know a more precise result and analysis.↵
↵
You can consider that I've preprocessed $[0,m]\cap\mathbb{Z}$ as a base case for the recursion (which doesn't seem to offer significant optimization).↵
↵
_English is not my native language; please excuse typing errors._
unordered_map<uint64_t, uint64_t> ump;↵
uint64_t solve(uint64_t n) {↵
if (ump.count(n))↵
return ump[n];↵
uint64_t p = cube(n - 1);↵
uint64_t c = p * p * p;↵
uint64_t res = solve(c) + solve(n - c) + (n - c);↵
ump[n] = res;↵
return res;↵
}↵
```↵
↵
I'm curious about the time complexity of this recursive function.↵
↵
Here, the function `cube` is used to calculate the **cube root** (not the cube). You can assume that it's $O(1)$ or $O(\log n)$.↵
↵
I believe it is $\Omega(\sqrt[3]{n})$, but I'd like to know a more precise result and analysis.↵
↵
You can consider that I've preprocessed $[0,m]\cap\mathbb{Z}$ as a base case for the recursion (which doesn't seem to offer significant optimization).↵
↵
_English is not my native language; please excuse typing errors._
