Help Needed in Time Complexity
Difference between en1 and en2, changed 0 character(s)
```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._

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English weily 2024-07-16 07:09:06 23 Tiny change: 'tion).\n\n_Engli' -> 'tion).\n\nCan anyone help me?\n\n_Engli'
en2 English weily 2024-07-16 06:06:13 0 (published)
en1 English weily 2024-07-16 06:04:36 819 Initial revision (saved to drafts)