annoying's blog

How I can find the time complexity of this algorithm?
By annoying, history, 4 years ago, In English

I tried to solve the problem on codechef problem COINS. And I have write the following code:

#define long long LL

map<LL,LL> data;   //map DS to store key:value pair
LL solve(LL n){
    if(n<=2)
      return n;
    if(data[n]==0){
      data[n] = max(n,(solve(n/4)+solve(n/3)+solve(n/2)));
    }
    return data[n];
}

This Link have a very nice discussion on time complexity of this code but I am not able to get any of that. can any one help me out to explain me in detail how can I approch to find the time complexity of this specific problem.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's O(log^2(n)) because you are using map to memoize your result so you never call a sub-tree multiple times. So your complexity will be number of calls * log(n) (because the complexity of the map data structure is log(n) per operation). The the number of calls will be at most log(n) because every time you divide n by 2 or 3 or 4 so the number of calls = how many operations needed to make n == 1 which is log(n). I think you can make the complexity O(log(n)) if you use a hash table. I am not sure about this. someone correct me

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe the complexity is something like $$$O(\log^2(n)\log\log n)$$$. While I can't prove it rigorusly, I have some ideas on how to prove it. Consider $$$n$$$ to be an integer that looks like $$$2^m3^l$$$. In this case the recursion will be called only for integers $$$2^{m_1}3^{l_1}, m_1 \leq m, l_1 \leq l$$$. There are no more than $$$\log^2(n)$$$ of those integers. At each call we will look though the map that contains $$$O(\log^2(n))$$$ elements, whilch results in additional $$$\log\log n$$$ factor.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For any integer $$$a$$$ and positive integers $$$b, c$$$, $$$floor(floor(a/b)/c)=floor(a/bc)$$$, so only the integers of form $$$floor(n/(2^p 3^q))$$$ will be passed onto the argument of the solve function. So your complexity is correct I think.

    → Reply