Find formula to describe recursion in method

Admin 1
Viewed 36

I am struggling with writing the formula that describes the recursive nature of the foo method.

Recursive function

The problem is that as far as I can tell, since every time n is divided with 2,

the binary tree formula should apply here.

This says that when in each call we divide the data we get a formula like this:

Recursion formula

And then if we analyze for 2 so enter image description here:

We get:

enter image description here

Which means that C(N) = log(N + 1), namely O(logN)

That all makes sense and seems to be the right choice for the foo method but it cant be because for

n = 8 I would get 3 + 1 iterations that are not n + 1 = 8 + 1 = 9 iterations

equation recursion complexity-theory algorithm
1 Answers

So here is your code:

void foo(int n) {
    if (n == 1) System.out.println("Last line I print");
    if (n > 1) {
        System.out.println("I am printing one more line");
        foo(n/2);
    }
}

We can write a recurrence relation down for its runtime T as a function of the value of the parameter passed into it, n:

T(1) = a, a constant
T(n) = b + T(n/2), b constant, n > 1

We can write out some values of T(n) for various values of n to see if a pattern emerges:

n    T(n)
---------
1    a
2    a + b
4    a + 2b
8    a + 3b
...
2^k  a + kb

So for n = 2^k, T(n) = a + kb. We can solve for k in terms of n as follows:

n = 2^k <=> k = log(n)

Then we recover the expression T(n) = a + blog(n). We can verify this expression works easily:

a + blog(1) = a, as required

a + blog(n) = b + (a + blog(n/2))
            = b + (a + b(log(n) - 1)
            = b + a + blog(n) - b
            = a + blog(n), as required

You can also use mathematical induction to do the same thing.

user_8472690
Related