On Wed, 2007-12-26 at 20:18 +0000, whm692003 wrote:
> Hi,
>
> This is my first post so please dont flame immediately!
>
> Can anyone lend any insight as to the possible answers for the
> following questions?
>
> Thanks!
>
> ~ Wm
>
> 1. explain the running time and space boundaries of the following
> function:
> int fib(int n) {
> if(n==1 || n==2) {
> return 1;
> } else {
> return fib(n-1) + fib(n-2);
> }
> }
>
I won't explain it, but ?I can point you in the direction you need. The
running time is O(n!) in Big "O" notation. It's an exponential solution.
Space boundaries? Not sure what that's asking for. Is it asking for the
boundaries of int or asking for the space requirements of an exponential
equation. I'd just say the space requirement is 2 times (because you
make 2 recursive calls at each level) the exponential of n.
> 2. explain how to use this structure, with special emphasis on the
> levels[0] member.
> struct MESSAGE (CMEBookUpdate, CMEMessage) {
> struct Level {
> Price buyPx;
> Price sellPx;
> int buyQuantity;
> int sellQuantity;
> int buyNumOrders;
> int sellNumOrders;
> };
> enum { MaxLevels = 6 };
> char tradingOrigin; // B=Book
> char tradingMode; // 0=Preopening 1=Opening
> 2=Continuous
> bool bookChanged[MaxLevels];// Has the N-th best order
> changed?
> Level levels[0]; // one level is present for each
> true in bookChanged
> };
>
>
>
>
>
