complexity 
Author Message
 complexity

Hi, there:

I've been stuck to complexity problem for a couple of days. I can't not
figure out what is them  for the following two:

1. (define crazy
       (lambda ( a b)
          (if (= b 0)
            a
            (+ (crazy (- a 1) (sub1 b))
                (crazy (+ a 1) (sub1 b))))))                      ;;;to find
its space complexity with big "O" notation

2.  (define funny
        (lambda (n)
            (if (<= n 0)
               0
               ( if (odd? n)
                  (+ 1 (funny (- n 3)))
                  (add1 (funny (funny (- n  4))))))))           ;;;to find
its time complexity with big "O" notation

Any clue is inspiring to my stale brain.

Frank



Wed, 23 Apr 2003 03:00:00 GMT  
 complexity

Quote:

>I've been stuck to complexity problem for a couple of days. I can't not
>figure out what is them  for the following two:
>1. (define crazy
>       (lambda ( a b)
>          (if (= b 0)
>            a
>            (+ (crazy (- a 1) (sub1 b))
>                (crazy (+ a 1) (sub1 b))))))                      ;;;to find
>its space complexity with big "O" notation

Well I can give you a definite answer: O(infinity) works for
both cases ;) Seriously though (assuming you are interested
in a slightly tighter upper bound), try drawing a recursion
tree of some sort to determine how many calls are necessary
and how much information needs to be kept for the evaluation
to complete. Make sure to establish the base cases and how
the recursive calls would eventually lead to them. Note that
the recursive calls are not tail-calls.

Quote:
>2.  (define funny
>        (lambda (n)
>            (if (<= n 0)
>               0
>               ( if (odd? n)
>                  (+ 1 (funny (- n 3)))
>                  (add1 (funny (funny (- n  4))))))))           ;;;to find
>its time complexity with big "O" notation

Interesting. This seems, on the surface, far less trivial than
the above space complexity problem (that is assuming that your
troubles with the other problem aren't entirely due to that
you're not as comfortable with the concept of space complexity).
I'd say try tracing this function with small values of n (make
sure to distinguish between odd values of n and even values of
n) to get a better idea of what it's computing. Then try to
define/establish the recurrence relation for the running time.
You might find it helpful to try to see what the function
returns first (and prove why it does).

--
It's difficult to see the picture when you are inside the frame.
                -- Anonymous



Wed, 23 Apr 2003 03:00:00 GMT  
 complexity
Thanks for your anonymous reply! But the correct answer for 1 is supposed to
be "O(n)"  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...

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.

Frank


Quote:

> >I've been stuck to complexity problem for a couple of days. I can't not
> >figure out what is them  for the following two:

> >1. (define crazy
> >       (lambda ( a b)
> >          (if (= b 0)
> >            a
> >            (+ (crazy (- a 1) (sub1 b))
> >                (crazy (+ a 1) (sub1 b))))))                      ;;;to
find
> >its space complexity with big "O" notation

> Well I can give you a definite answer: O(infinity) works for
> both cases ;) Seriously though (assuming you are interested
> in a slightly tighter upper bound), try drawing a recursion
> tree of some sort to determine how many calls are necessary
> and how much information needs to be kept for the evaluation
> to complete. Make sure to establish the base cases and how
> the recursive calls would eventually lead to them. Note that
> the recursive calls are not tail-calls.

> >2.  (define funny
> >        (lambda (n)
> >            (if (<= n 0)
> >               0
> >               ( if (odd? n)
> >                  (+ 1 (funny (- n 3)))
> >                  (add1 (funny (funny (- n  4))))))))           ;;;to
find
> >its time complexity with big "O" notation

> Interesting. This seems, on the surface, far less trivial than
> the above space complexity problem (that is assuming that your
> troubles with the other problem aren't entirely due to that
> you're not as comfortable with the concept of space complexity).
> I'd say try tracing this function with small values of n (make
> sure to distinguish between odd values of n and even values of
> n) to get a better idea of what it's computing. Then try to
> define/establish the recurrence relation for the running time.
> You might find it helpful to try to see what the function
> returns first (and prove why it does).

> --
> It's difficult to see the picture when you are inside the frame.
>                 -- Anonymous



Wed, 23 Apr 2003 03:00:00 GMT  
 complexity

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



Thu, 24 Apr 2003 09:46:19 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Space complexity of J programs

2. Question on complexity

3. Form Complexity??

4. Shrinking from Complexity

5. Shrinking from Complexity

6. Computational Complexity of Functional Program

7. Questions about time complexity of functional programming

8. Question: amortized complexity of Queue implementation

9. JFP Special Issue on Functional Programming and Computational Complexity

10. DIMACS Workshop on Computational Complexity and Programming Languages,

11. a complexity result about lazy evaluation being better than eager

12. higher-order complexity

 

 
Powered by phpBB® Forum Software