beregning af køretids-orden for funktion. O(___)

Jeg har leget med fibonacci tal og lavet forskellige metoder til udregning af fibonacci(n).

Men jeg kan ikke finde en god måde a beslutte hvilken orden metoden L i den lille lære-klasse (LearnFib) skal have. Det er nemt at se a den efterhånden tenderer imod konstant tid O(k), men før den kommer såvidt er den hvad ???


import java.io.*;
import java.lang.*;

class LearnFib {
   
    private static long[] memory = new long[100];
   
    public LearnFib ( ) {
        memory[0] = 0;
        memory[1] = 1;
        for (int i=2; i<memory.length; i++ ) memory[i] = -1;
    } //endconstructor LearnFib
   
    public long L ( int nr ) {
        if ( memory[nr] >= 0 ) return memory[nr];
        return ( memory[nr] = L(nr-1) +L(nr-2) );
    } //endmethod L  Order ?? funktion
   
} //endclass LearnFib

public class TestFib {
 
    public static long fibOn ( int nr ) {
        long[] acc = { 0, 1 };
        int i;
        for ( i=0; i<nr; ) {
            acc[i&1] += acc[++i&1];
        }
        return acc[i&1];
    } //end fibonacci Order N function
 
    public static long fibOnn ( int nr ) {
        switch (nr) {
          case  0: return 0;
          case  1: return 1;
          default: return fibOnn(nr-1) +fibOn(nr-2);
        }
    } //end fibonacci Order N^2 function
 
    public static long fibOEn ( int nr ) {
        switch (nr) {
          case  0: return 0;
          case  1: return 1;
          default: return fibOEn(nr-1) +fibOEn(nr-2);
        }
    } //end fibonacci Order 2^N function
 
    public static void main (String[] args) {
        LearnFib fib = new LearnFib();
        for (int i=0; i<40; i++ ) {
            System.out.println ( "O(L?) " +i + " giver " +fib.L( i ) );
            System.out.println ( "O(n)  " +i + " giver " +fibOn( i ) );
            System.out.println ( "O(nn) " +i + " giver " +fibOnn( i ) );
            System.out.println ( "O(En) " +i + " giver " +fibOEn( i ) );
        }
    } //end main

} //endclass TestFib

( og hvorfor pokker er det forbudt at skrive '?' efter efter spørgsmålet i titlen )

mvh JakobA