more recursions, by popular (Alba's) demand

[wood]

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

Indeed!!


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).

Look at AlbaLed's explanation and mine for the runtime. It is definitely not linear.. I ran a program and after 50, my pentium IV at work was crawling! Why isn't it O(3^N)?

[AlbaLed]

n permute n-1

hahahaha

[nonevent99]

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

You're probably right that there's an asymptotically tighter bound than log3(n). I don't know how to get it off the top of my head, though. The problem is that 3 isn't a power of 2. If somebody had said a(n) = a(n/2) + a(n/4), then I'd say that computing the left hand subtree of a(n) is twice as expensive as computing the right hand subtree. So R(n) = 2*R(n/4) + R(n/4) (where R = runtime) = 3*R(n/4), which has a nice clean solution using the master theorem.

Hm. Is it true that computing the left hand subtree is twice as expensive as the right hand? I'm not so good with trees.

[nonevent99]

Originally posted by wood

Indeed!!


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).

Look at AlbaLed's explanation and mine for the runtime. It is definitely not linear.. I ran a program and after 50, my pentium IV at work was crawling! Why isn't it O(3^N)?

It's those kind of cavalier statements that'll get me a 630 on this exam if I'm not careful! [V] The run time is essentially the same as if we had to calculate the run time of b(n) = b(n-1) + b(n-2), ie computing the Fibonnaci. We hashed through that in another thread.

http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8613

[nonevent99]

Originally posted by 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);
}

Yup, typo. Definite typo. :drunk:

So you're both right!

[wood]

Hehehe... don't worry... I'll be the one with 630 and you'll get around 890 or so... !! I do VERY poorly in timed exams... somehow I get nervous and start trembling, etc. I never liked it. Millions things passed through my mind. Hard to focus!! Anyway... We'll all try our best.

Wood

[AlbaLed]

In my opinion as long as you get the idea, ie. log(n), c^n, the base of the log or the c in the exponential will not matter, because you're describing a big OH notation, not exact. So as long as you get whether it is linear, log, poly or expo I think it does not matter anymore. If asked for exact that's when constants come to play

[nonevent99]

Phehw. Last two.

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

Well, if we didn't have the f or e, we'd just have O(n). The f(n) was n! or 0, depending on whether you guessed that I had a typo. e(n) was (lgn)!, in case you didn't realize that, based on my comment above. If you take the correct value for f(n), I guess that g(n) must be a little bigger than n!, but not bigger than n*n!, so O( ((n+1)!) ) will work here. I don't see a quick way to get a tighter bound.




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

Let a = 2, b = 2, r = log(a base b) = 1. n*lg n = Big Omega (n^r). It also satisfies a*(n/b)*(lg n/b) < c*n*lgn for some c < 1.

Master's Theorem applies. So the answer is O(n*lgn)

[AlbaLed]

wood, with all this practice we're getting we probably talk about this stuff in our sleep. Don't worry dude, we're doing the best all of us can, smth that by ourselves we could have never done, so believe in the power of team, and get in the exam concious that all of us are with you and kick butt, after you;re done share a drink with us :drunk:

[nonevent99]

Originally posted by wood

Hehehe... don't worry... I'll be the one with 630 and you'll get around 890 or so... !! I do VERY poorly in timed exams... somehow I get nervous and start trembling, etc. I never liked it. Millions things passed through my mind. Hard to focus!! Anyway... We'll all try our best.

Wood

Wood, you still have a few days to try and practice under "real" conditions. Take a couple hours each night and do the test from ETS. Yeah, it's the same problems over and over, but the experience really helps.

I used to tremble, too, and sweat a lot. Now it's not so bad.

One big problem I have right now is that my mind wants to move onto the next problem as soon as I think I understand the answer to the current problem. At that moment, I start filling in the bubble without really thinking about what I'm doing, and I sometimes fill in the wrong bubble!!!!!

SO the past few weeks, I've been practicing filling in bubbles as I do practice problems. It seems to be helping.