Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -1 down vote favorite 
public static int abc(int n) {
    if (n <= 2) return n;

    int sum = 0;
    for (int j=1; j<n; j *= 2)
        sum += j;

    for (int k=n; k>1; k /= 2)
        sum += k;

    return abc(n – 1) + sum;
}

Hi there, may I know the time complexity (in big-O notation) of the following recursive code?

My answer is O(nlogn).

Just wish to check if I am correct? :)

share|improve this question
not fair, you just changed your answer, yes i think you are now correct... – Joe Apr 22 at 4:03
Hi Joe. I just realised I made a mistake. May I know what is your answer? – Lawrence Wong Apr 22 at 4:05
Don't think so. Its easier to see when you use loops. But converting this recursion into a loop is trivial. – Loki Astari Apr 22 at 4:32
1  
Hello Lawrence and welcome! Please do not post exactly the same question on more than one sites, you've already posted this on Stack Overflow. We can move questions between sites automatically if you happen to post at the wrong site, so there's really no reason to post on more than one sites. Furthermore it's always better if all possible answers to the question are on one place, so they'll be easier to find by people having the same problem. Since the Stack Overflow version of your question already got an answer, I opted to close this version. – Yannis Rizos♦ Apr 22 at 4:55

closed as off topic by Yannis Rizos♦ Apr 22 at 4:52

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.