What is complexity of this function?

Revision en1, by tom, 2016-02-02 15:25:03
int highest(long long n) {
    int r = 0;
    while(n) {
        r++;
        n >>= 1;
    }
    return r-1;
}

int dfs(long long n) {
    if(n == 0) return 0;
    int h = highest(n);
    long long n1 = n-(1LL<<h);
    long long n2 = (1LL<<(h+1))-n;
    int res = 1+dfs(n1);
    if(n2 < n) res = min(res, 1+dfs(n2));
    return res;
}

What is complexity of dfs(n) and why?

Tags complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tom 2016-02-02 15:25:03 446 Initial revision (published)