more recursions, by popular (Alba's) demand

[nonevent99]

Here are some more to practice on. Solve for the function as a big-O of n, and also give the run-time as a big-O of n.

function a(n) {
if (n <= 1) return 1;
return a(n/3) + a(n/2);
}

function b(n) {
if (n <= 2) return n;
return a(n-1) + 2*a(n-2);
}

function c(n) {
if (n <= 1) return n;
return c(floor(log(n))) + e^n;
}

function d(n) {
if (n <= 1) return 1;
return 2*d(n%(n/2));
}

function e(n) {
if (n <= 2) return 1;
return e(n/2)* lg(n);
}

function f(n) {
if (n <= 3) return n % 3;
return n*f(n-1);
}

function g(n) {
if (n <= 10) return n;
return g(n-1) + f(n-2) + e(n-3);
}


function h(n) {
if (n <= 10) return n;
return 2*h(n/2) + n*lgn;
}

Good luck!

[AlbaLed]

function b(n) {
if (n <= 2) return n;
return a(n-1) + 2*a(n-2);
}

Is there a typo, a(n-1) should it be b(n-1) or not?

[wood]

I believe so...

function a(n) {
if (n <= 1) return 1;
return a(n/3) + a(n/2);
}

a(n) = O(n)
run time = O(log n)


function b(n) {
if (n <= 2) return n;
return a(n-1) + 2*a(n-2);
}

b(n) = O(3^n)
run time = O(n)

[AlbaLed]

Wood I don't think you got the runtime of b correct

b(n) = b(n-1) + b(n-2) <= 2b(n-1)

if we build and execution tree, it is going to be a binary tree, with height n - 1, the number of nodes in the tree give us the number of calls, which is going to be 2^n. Am I missing an important part here ??? Try the real tree with n= 6, I am getting 15 calls, and n=5 yields 9 calls

b(7)  = b(6) +  b(5) = 24
b(8)  = b(7) +  b(6) = 24 + 15 = 39
b(9)  = b(8) +  b(7) = 39 + 24 = 63
b(10) = b(9) +  b(8) = 63 + 39 = 102

that does not seem like a linear growth to me. what do you think?

[wood]

You're right AlbaLed. Somehow, I have trouble calculating the running time. So, in this case it is 2^(n-1) + 2^(n-2), right? We bound it to what, 2^N?

[AlbaLed]

there you go 2^n. I find it really helpfull building a tree, even in the other case when you have to compute the big-oh of the function, you have a tree, not binary anymore but ternary, (n-1) (n-2) (n-2). Don't know if this is going to work for you but it definitely works for me. Screw the master theorem, as long as you know how to do summations correctly you can always solve a recurrence by building a tree, I usually do a tree of heigh 3, because that's when the patterns become visible and let the summation take over from there. Try it, it might work for you too

hope it helps

[wood]

AlbaLed... I usually try the iteration method or a tree. I usually swing between both and because of that I lose time sometimes.

Let me try the other ones...

[wood]

In C, it is supposed to be ln instead of log right?

function c(n) {
if (n <= 1) return n;
return c(floor(ln(n))) + e^n;
}

?

function d(n) {
if (n <= 1) return 1;
return 2*d(n%(n/2));
}

d(n) = 2
run time = 2

[AlbaLed]

function c(n) {
if (n <= 1) return n;
return c(floor(log(n))) + e^n;
}
run time O(log*(n))
function = e^n + e^log(n) + e^log(log(n)) ..... no clue about this series

function d(n) {
if (n <= 1) return 1;
return 2*d(n%(n/2));
}

run time = O(1)
function = O(1)

function e(n) {
if (n <= 2) return 1;
return e(n/2)* lg(n);
}

run time = O(lg(n))
function = lg(n)*lg(n/2)*lg(n/4)* ....... =
= lg(n)(lg(n) - 1)(lg(n) -2) ...... *(lg(n) - [lg(n) - 1]), so I guess we could say
function = O[lg(n)^lg*(n)] ???? nonevent can you confirm

[wood]

Right AlbaLed... I got the same thing and was about to post. O(ln(n)^log(n))

Wood