3/27    What's the running time (big-O) of fibonacci series? I can't find it
        on CLR. It only talks about the golden ratio shit.
                 \_ F_n=(p^n-(1-p)^n)/sqrt(5), p=the golden ratio. --Galen
        \_ CLR was the most worthless piece of shit book I have spent my
           money on.  It's worth more as fire wood or a shooting target than
           an academic textbood.
           as an academic textbook.
           \_ Go read some Sesame Street literature, then. There's a good
              REASON that CLR is the single most popular intro algorithms
              text in the world.
        \_ O(1).
           \_ dumbass
        \_ A numeric sequence can't have a running time, only an algorithm
           can.  Please restate your question.  Also, Fibonacci numbers are a
           sequence, not a series.
           \_ How about "What's the running time of evaluating the n+1-th
              number in the Fibonacci sequence F(n) by using the recursive
              algorith F(n)=F(n-1)+F(n-2), F(1)=F(0)=1?"
              \_ The naive implementation is exponential, the slightly less
                 naive memoizing implementation is linear.
              \_ The cool implementation is constant time.  You can derive
                 a formula like F(n) = a * b^n + c * d^n.  I don't remember
                 the coefficients, but you can look them up or derive them.
                 If you need the formula and you can't find it, email me
                 and I'll take the time to derive the constants. -emin
                 \_ F_n=(p^n+(1-p)^n)/sqrt(5), p=the golden ratio. --Galen
                 \_ uh, if you have to use "to the power of n", for arbitrary
                    n, i don't think it's constant time...nice try though.
                    \_ "To the power of" is O(1).  Nice try though.
                       \_ I'm impressed...with your stupidity.  I mean,
                          you can't really be THAT clueless can you?  You'd
                          have to be TRYING to be stupid to come off that well.
                          I really hope you were expressing something in an
                          odd and painfully obtuse way rather than blithering
                          utter and complete nonsense.
                       \_ Go read a book, moron. Let's see you do O(1)
                          ANYTHING. O(1) means you don't even have time
                          to read the entire input. Exponentiation in
                          arbitrary precision is O(log) with respect to the
                          exponent. Actually something like O(n^3) w.r.t.
                          actual input size, since the base has to be
                          multiplied by itself O(log(exponent)) times.
        \_ BTW, what's the Fibonacci series famous for?  It might be useful
           for teaching computer science, but for math itself what's it
           useful for?
           \_ It comes up in the wierdest places.  People have used the
              fibonacci sequence to analyze the stock market (successfully).
              \_ yep. there is a journal called the "fiboonacci quarterly"
                 devoted entierely to such weird cases.  it should be in
                 the math library if you're interested.
              \_ If the stock market was that easily analysed, we'd all be
                 billionaires.
                 \_ you mean you're *not* a billionaire?
                        \_ I meant the rest of you peasants.
           \_ Modeling the reproduction rate of rabbits.
        \_ yeah, i hear you on that one.  the most i've ever seen it
           for is the continuous torture of students throught junior high,
           high school, and college.  if anybody can actually point out
           a url which proves that this thing actually has a practical
           application in reality, i'd be really pleased to see it...
           die, fibonacci, die!!!
           \_ Torture?  Fib series is trivial.  Where'd you go to school?
              Dummy High?
           \_ C is for Coo^WYour Grade and it's good enough for you!
           \_ If that's the most you've ever seen it used for, you must
              be an inexperienced college kid with little view of the
              wider world beyond the school walls.  That puts you in the
              right place.
           \_ for modeling the rate of spawning of new rabits in the wild -ali
                \_ This is important because....?
                  \_ because it also models the rate at which i and my progeny
                     have been doing your mom for the past two years. -ali
        \_ Try Fibonacci heaps.
           \_ Whatever.  The complexity of the heap operations incur so
              much overhead that they eventually end up costing a lot
              more to implement than with an alternative and simpler
              implementation thus cancelling out any improvements gained
              from lower running times.  This is as useless as Straussman's
              (sorry if I spelled his name wrong Ilyas). Big deal. We can
              matrix multiply in O(n^2.7) time instead of O(n^3). It turns
              out to run slower on most machines anyways so why bother.
              \_ what the fuck are you talking about?  name another data
                 structure that implements priority queues with logn insert
                 and 1 retrive. the "simpler" alternative you have in mind,
                 is it an insertion sort or something stupid?
                 \_ Maybe he is talking about standard heaps which have logn
                    insert.
              \_ Strassen's is getting to be O(n^2.3) now.  And even the
                 O(n^2.7) implementation becomes faster than normal
                 multiplication for sufficiently large arrays on the machines
                 where 170 homework is done, at least. -- ilyas
                 \_ The best known, n^2.376, isn't based on Strassen-Winograd
                    original... not that it matters, of course...
              \_ Do you have any idea how big the matrices for interesting
                 real-world problems tend to be?  Do you have any idea
                 how much less (n^2.7) is than (n^3)?    -blojo
                 \_ Why, do YOU? Because it isn't all that large. Even a lame
                    implementation passes the threshold at about 150x150
                    matrices. A _lot_ of problems involve much larger matrices
                    which are sufficiently dense for sparse methods not to
                    work.
                    \_ Are you arguing for or against Strassen's?
                    \_ That's not how it is in my industry (games).
                       Nobody doing a complex system will write brute-force
                       matrix math and expect it to run okay.  It's all
                       about multigrid methods, frequency-space operations,
                       you name it.     -blojo
                       \_ while (player_still_alive()) {draw_dot(x,y);}
              \_ Ideas similiar to Strassen's algorithm are used for
                 fast FIR filtering which is widely used in all sorts
                 of DSP algorithms.  I don't know if people thought of
                 fast FIR filtering first or Strassen's algoirthm first.
                 However, the point is that the ideas behind Strassen's
                 algorithm turn out to be very useful.  IMHO the reason
                 to study algorithms (even weird stuff like Strassen's
                 algorithm and Fibonacci heaps) is so that when you
                 have a particular practical problem you can come up
                 with clever ideas. -emin
                 \_ Strassen was there first.
        \_ I'm sorry, Strassen's should *never* be faster on modern
           architectures, where multiplies are as fast as adds. Strassen's
           trades off more adds for fewer multiplies. As long as you've
           blocked your implementation for cache and registers, and copied
           when you have low-associativity caches or TLB, then you're OK
           without Strassen's.   -nick
           \_ Uh, go read the book again. Strassen optimizes away MATRIX
              multiplies, NOT scalar multiplies. If we knew how to multiply
              matrices as fast as we can add them (O(n^2)), all of Strassen's
                      instead of 8 muls, you have 7 muls. -ali
              stuff would be obsolete, yes.... But we _don't_
                        \_ Isn't this one of the advantages of a Quantum
                           Computer over standard computers.
                           \_ Oh, shut the fuck up, and consult the literature.
                \_ Find a new book.  At the instruction level, a multiply is
                   a multiply.  Thank you for playing.
                   \_ Wow.  Are you just a total idiot or what?  For a square
                      matrix of size n x n, addition or scalar multiplication
                      requires O(n^2) operations, whereas naive matrix
                      multiplication requires O(n^3) opations.  Yes, add and
                      mul are single instructions, but Strassen attempts to
                      reduce the number of those instructions.
                        \_ This was exactly my point.  So there's no reason,
                           as you said, why we should use add instead of mult.
                           \_ because while add and mult are equally fast,
                              add is faster than mult.  Duh! --pld
                   \_ look, strassen's replaces a multiply by 14 adds so that
                      instead of 8 matrix muls, you have 7 matrix muls. -ali
                        \_ Thank you for reaffirming my point that an mult is
                           the same difficulty computationally as an add, so
                           there's no need for all these Strassen methods and
                           their variants.
                           \_ it replaces 1 matrix multiply by 14 matrix adds.
                              A matrix mutliply (brute force) is O(n^3).  A
                              matrix add is O(n^2).  are you really this dense?
                              \_ But they're the same if n is 1, so fuck you!
        \_ I think you can use a generating function z() to compute the nth
           fib. number in constant time-  hence the O(1).
           \_ Formatting fixed.
           \_ The above function IS the generating function and it's NOT
              O(1) with respect to input size. Read above posts.
                \_ Think outside the box.  The answer is there if only you
                   would reach for it.
           \_ i think bigdickbastardpedant's complaint is that you can't
              generally compute e^x in constant time, because you need to
              compute at least a taylor series or something, and the number
              of terms used does depend on x, as larger x's are more poorly
              approximated with few terms. i don't know of a way to compute
              e^x in time independent of x either. -ali
              \_ "Hello, Pedant." *clickety click*
              \_ Well The Pedant needs to go re-read exactly what O() notation
                 is all about and how to properly compute it.  The size of the
                 input is unrelated to the O(), therefore The Pedant is not
                 only a pedantic idiot, but is simply flat out wrong as well.
                 \_ you must have this strange verison of O() notation that
                    depends on the phase of the moon or something.
                 \_ If sorting is O(n log n), what does n measure? lumen? -pld
       \_ fibonacci sucks big dick
          \_ I wish. but mine wont fit
             \_ You wish a guy suck your dick?
                \_ You wish your writing good grammar?
                \_ Why not?  Who cares who does it?  Lips & tounge are
                        lips & tounge.
                   \_ Sigh.
                      \_ Ahhh.
                   \_ Is formatting so hard?  I think I'll start purging all
                      content-free comments that are poorly formatted.
                                --formatting nazi
                      \_ Do it.  Blow 'em away!
                   \_ what the fuck is a tounge?
                      \_ An extremely clever anagram.