From: 643-408-1753@kylheku.com   
      
   On 2025-10-24, 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.   
   >   
   > You also don't say that 'insertion sort' is O((N^2)/2); it's O(N^2).   
      
   I think, whereas constant factors and constant terms are understood not   
   to matter in asymptotic complexity, the choice of exponential base in   
   exponential complexity does. Similarly to the choice of exponent   
   in the category of polynomial time: e.g. cubic is slower than quadratic.   
      
   If we have 1 < a < b  then O(b^n) is a faster growth than O(a^n).   
      
   2^n doubles with every increment in n.   
      
   Whereas 1.02^n doubles --- here we can use the 'rule of 72' from   
   finance --- for a +36 increase in n.   
      
   If spending twice the computing time buys us only a +1 increase in   
   the input parameter n, versus +36, that's a big deal.   
      
   A term added to n in in 2^n wouldn't matter because 2^(n+c)   
   is (2^c)(2^n) translating to a constant factor. But a coefficient   
   on n would matter: 2^(kn) = (2^k)^n. It changes the base.   
      
   --   
   TXR Programming Language: http://nongnu.org/txr   
   Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal   
   Mastodon: @Kazinator@mstdn.ca   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)