From: antispam@fricas.org   
      
   Janis Papanagnou  wrote:   
   > On 24.10.2025 16:35, Michael S wrote:   
   >> On Fri, 24 Oct 2025 15:36:58 +0200   
   >> Janis Papanagnou  wrote:   
   >>   
   >>> On 24.10.2025 09:53, Rosario19 wrote:   
   >>>>   
   >>>>   
   >>>>> into the above pair of functions, or anything similar.   
   >>>>>   
   >>>>> That's not ordinary optimization of the type which improves the   
   >>>>> code generated for the user's algorithm; that's recognizing and   
   >>>>> redesigning the algorithm.   
   >>>>>   
   >>>>> The line between those is blurred, but not /that/ blurred.   
   >>>>   
   >>>> int fib1(int n){return fib_tail(0, 1, n);}   
   >>>>   
   >>>> is different from   
   >>>>   
   >>>> int fib(int n){if(n<2) return 1;return fib(n - 1) + fib(n - 2);   
   >>>>   
   >>>>   
   >>>> both these function calculate from the 0 1  the number result, but   
   >>>> fib() start to calculate from n goes dowwn until n=0, than goes up   
   >>>> until n=input, instead fib1() go only down for n. It seen the calls   
   >>>> (fib has 2 call each call... instead fib_tail() just 1), I think   
   >>>> fib() is O(n^2) instead fib1 is O(n).   
   >>>   
   >>> It's worse; it's O(2^N).   
   >>>   
   >>> Janis   
   >>>   
   >>   
   >> 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.   
      
   Look and learn.  True values of parameters frequently are irrational   
   and sometimes there is no explicit formula.  Decimals allow easy and   
   reasonably good comparison of complexity classes.   
      
   And to be clear: O((4/3)^n) and O(1.332^n) are two different Landau   
   symbols corresponding to two different complexity classes.   
      
   Strictly speaking 1.618 above is wrong, 1.618 < phi where phi is the   
   golden ratio, so corresponding class is lower (smaller) than O(phi^n)   
   (which is correct complexity class).  But using decimal approximation   
   gives reasonably good feel of the complexity and is established   
   practice when writing about complexity results.   
      
   --   
                                 Waldek Hebisch   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)