How to calculate value of the recursive function?

Question

I have the recursive function: T(n) = 2T(n/2) + n. I want to find the complexity of the function by passing different arguments to the function and getting values of the function. Then I will guess the formula of the function(e.g n, n*log(n)).

I write the following code:

public static void main(String[] args) {
    System.out.println(findValueOfTheFunction(2));
    System.out.println(findValueOfTheFunction(4));
    System.out.println(findValueOfTheFunction(8));
}

static double findValueOfTheFunction(double n) {
    if(n > eps) {
        return 2*findValueOfTheFunction(n/2) + n;
    }
    else return 0;
}}

I get three points from the code. p1(2, 10) and p2(4, 24) and p3(8, 56).

As a understand, the complexity of the recursive function is O(n) = n*log(n). But my points doesn't fit to the formula.

I've done some research here, but nobody seems to have similar issue.

Answer 1

Your very first problem is here:

 else return 0;

At some point; your recursion ends; and reaches that if.

And then you start multiplying the result of that last call ... and guess what x * y * z * ... * 0 might compute to?!

So all your method is doing is returning some m * n value (where n is your input; and m depends on how often you recursively call your own method. As your code translates to:

  if (n>eps) {
    return n + findValueOfTheFunction(n/2)

Long story short: your computation looses the "interesting" part of its result. So - instead of returning 0 ... return 1!