From: jameskuyper@alumni.caltech.edu   
      
   On 2025-10-27 16:33, Michael S wrote:   
   > On Mon, 27 Oct 2025 14:41:11 -0400   
   > James Kuyper  wrote:   
   >   
   >> On 2025-10-27 07:52, Janis Papanagnou wrote:   
   >>> On 27.10.2025 10:48, James Kuyper wrote:   
   >>>> On 2025-10-24 11:22, Janis Papanagnou wrote:   
   >>>>> On 24.10.2025 16:35, Michael S wrote:   
   >>>> ...>> Actually, the number of calls in naive recursive variant =   
   >>>> 2*FIB(N)-1.   
   >>>>>> So, O(1.618**n) - a little less bad than your suggestion.   
   >>>>>   
   >>>>> It's new to me that O-complexities would be written with   
   >>>>> decimals.   
   >>>>   
   >>>> Complexities are determined by the highest power of the relevant   
   >>>> parameter; that power needn't be integral, though it usually is.   
   >>>> I'd be interested in the derivation of that result.   
   >>   
   >> My apologies. For some reason I read that at N^1.618, not 1.618^N.   
   >   
   > IMHO, you don't have to apologize. Janis's arguamnet make no sense   
   > inboth cases.   
   I wasn't addressing his argument, only his comment about (so I thought)   
   whether you could have a complexity of O(N^1.618), which would lie   
   between O(N) and O(N^2). O(1.618^N) is a very different thing; I think,   
   for sufficiently large N, it's higher than any polynomial. I think   
   they're both legitimate possibilities, but I would be very interested in   
   the derivation of either one.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)