Quote:

>Thanks for your anonymous reply!

Uhm, not quite sure what was so anonymous about my reply. I'm

far less anonymous than anyone who's posting through an ISP,

real name or not.

Quote:

>But the correct answer for 1 is supposed to

>be "O(n)"

Correct. Note that the Big-O notation only tells you about

its (asymptotic) upper bound. In other words, any function

that is O(n) is also O(n^2), O(n^3), etc. Usually you want

the tightest possible upper bound, but technically speaking,

it's not a requirement when you're asked to give the

complexity in Big-O.

Quote:

>that is quite confusing by analyzing like this:

>n=1: the number of "droid model": 1 droid waiting there for values being

>passed by returns of other tow to be called that count "null" by "droid

>model" because they are called and instantly return and pass the values to

>the droid calling them, although they might take considerable time for

>execution of all recursions, in this case, two extra. When n=2, still one

>droid (crazy a 2) will be waiting there for all other 6 recursions' return

>when reaching to base n=0. What confuses me so much is why initial call of

>crazy count to droid number while other recursively called not...

Well the calls are not made in parallel. You don't make the

second call until the first call returns. If you draw the

recursion tree, or trace the evaluation, you'd see there are

at most n recursive calls at any given time.

Quote:

>It seems more tedious for 2 because it appears for the second term of the

>body to approach base in much more complicated way than the first term for

>it includes both odd and even cases and nested funny to trace. To me, it

>seems too complicated to get exact image for it with a fair big n.

Let's say the value of the function for input n is V(n) and

its running time for input n is T(n).

Then you have

if n is odd and greater than 0

T(n) = T(n - 3) + C

if n is even and greater than 0

T(n) = T(n - 4) + T(V(n - 4)) + C

if n is zero or less

T(n) = C

In order to solve this recurrence, it's probably necessary

to come up with an idea of what V(n) is for a typical n.

(Use induction!)

--

We seldom repent talking too little, but very often talking too much.

-- Jean de la Bruyere