Go Back   TestMagic Forums > Test preparation > GRE Subject Tests > GRE Computer Science
Register Forum Rules FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
Old 2003 November 2nd, 07:17 PM   #21 (permalink)
TestMagic Guru
 
Join Date: Jul 2003
Location: Brazil
Posts: 1,360
wood has disabled reputation
Quote:
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)?

wood is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:18 PM   #22 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: Albania
Posts: 534
AlbaLed has disabled reputation
n permute n-1

hahahaha
AlbaLed is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:18 PM   #23 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: USA
Posts: 508
nonevent99 has disabled reputation
Quote:
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 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:20 PM   #24 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: USA
Posts: 508
nonevent99 has disabled reputation
Quote:
Originally posted by wood

Quote:
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)?

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 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:23 PM   #25 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: USA
Posts: 508
nonevent99 has disabled reputation
Quote:
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!
nonevent99 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:24 PM   #26 (permalink)
TestMagic Guru
 
Join Date: Jul 2003
Location: Brazil
Posts: 1,360
wood has disabled reputation
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 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:27 PM   #27 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: Albania
Posts: 534
AlbaLed has disabled reputation
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
AlbaLed is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:28 PM   #28 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: USA
Posts: 508
nonevent99 has disabled reputation
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)
nonevent99 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:31 PM   #29 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: Albania
Posts: 534
AlbaLed has disabled reputation
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:
AlbaLed is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2003 November 2nd, 07:31 PM   #30 (permalink)
TestMagic Guru-in-Training
 
Join Date: Oct 2003
Location: USA
Posts: 508
nonevent99 has disabled reputation
Quote:
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.
nonevent99 is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

What you can do
You cannot post new threads
You cannot post replies
You cannot post attachments
You cannot edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


All times are GMT. The time now is 01:13 AM.

Contact TestMagic   TestMagic Forums      Archive   Privacy Statement

TestMagic Locations   Legal   Privacy


SEO by vBSEO 3.2.0
Copyright © 2009 TestMagic
Ad Management by RedTyger

Scroll Up