Help Needed in Time Complexity

Revision en1, by weily, 2024-07-16 06:04:36
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.

Tags time complexity

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)