more recursions, by popular (Alba's) demand

[AlbaLed]

how did you get that, enlighten us all por favor, El Señor

[wood]

Well, pretty much the same logic as you posted.

The run time is O(log(n)) (by log(n) I mean log n base 2), since we keep dividing it by 2.

The function is

ln(n)*ln(n/2)*ln(n/4)*... for log(n)-1 times.

ln(n)*(ln(n)-ln(2))*(ln(n)-ln(4))*...*(ln(n)-(log(n)-1))
[ln(n)^2 - ln(n)*ln(2)]*(ln(n)-ln(4))*...
[ln(n)^3 - ln(n)^2*ln(4) - ln(n)^2*ln(2)]*...

So, if you multiply it by log(n)-1 times, the first part of the function will be ln(n)^log(n) and we can bound to it.

Does it make sense? Am I completely off?

[wood]

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

f(n) = for n>=3, I'd say f(n) = 0 ?
run time = O(n)

[AlbaLed]

It does make sense, but one part that you're loosing me is why do you switch to ln(n).

For f(n) I guess you can put O(1), and your runtime is good.
Another case is, if nonevent is looking for is actually calls to f(n) if this was a recurrence problems like this

f(n) = n%3 (n =1,2,3)
f(n) = nf(n-1)

which is then going to be n!/3!, and then the recurrence start to unroll.

The above might be the case if nonevent made a typo, instead of writing

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

[wood]

Ops... my mistake. Somehow, I thought that it was ln() from the definition of e(). It is therefore O(log(n)^log(n)).

[nonevent99]

a(n) = a(n/3) + a(n/2);

Did you guys try plugging this into a piece of software and actually try calculating it? It's instructive. a(n) definitely doesn't grow as fast as n. So you could say it's O(n), but there is a tighter bound.

If you guess that a(n) = O(n^p) for some p that we need to discover, then you can suppose that a(n) = k * n^p for really big n. Substituting, a(n) = k * (n/2)^p + k * (n/3) ^ p. If we set this equal to a(n) = k * n^p, we find that k needs to solve k /2^p + k/3^p = 1. Trying out various values of p, I find that k = 1, p = 0.78 quantitatively matches what I get if I write a piece of software to compute a.

So a(n) is approximately Theta(n^0.78).

Obviously, on the GRE we won't have recourse to software. But there is a lesson here: If the problem had been a(n) = 2*a(n/2), then obviously the answer would be a(n) = O(n). But here we only have a(n/3) + a(n/2). It turns out that this makes an asymptotic difference in the function's value.

I hope you think that's as cool as I do.

The run-time should be log (n base 3) because that's what it takes to drive n down to 1.



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

Definitely O(2^(n-1)), as calculating a few will tell. Run time O(n).

[nonevent99]

Originally posted by 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

That looks right, so it's e^n + n + log(n) + log(log(n)) + ...

which I think can be bounded above by e^n + 2*n, yielding O(e^n).

[nonevent99]

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

You guys got this one. Pretty much always equals 2 (exception is n <= 1) after only one iteration.

[AlbaLed]

nice catch on
a(n) = a(n/3) + a(n/2);

Do you know of any faster way to work on this problem, because you cannot assume a(n) <= 2a(n/3).

The run-time should be log (n base 3) because that's what it takes to drive n down to 1.

True, for the left most part of recursion, what about the n/2 side??? Isn't big OH supposed to capture the max, wors case time? Eventhough it does not make any difference because log3(n) is only a constant factor away from lg(n), I want to make sure I get you're line of thinking.

[nonevent99]

This is probably the coolest of all the functions I posted.

n    e(n)  lg n  
1    1       0 
2    1       1 
4    2       2 
8    6       3 
16   24      4 
32   120     5 
64   720     6 
128  5040    7 
256  40320   8 
512  362880  9

Recognize the sequence?