Fibonacci ali sa O(n)

Code:

using System;

namespace ConsoleApplication2
{
    /// <summary>
    /// Summary description for Class1.
    /// </summary>
    class Class1
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main(string[] args)
        {
            //
            // TODO: Add code to start application here
            //

            int a;
            int b;
            fib (7, out a, out b);
        }

        static void fib(int i, out int sa, out int sb) 
        {
            int sc;
            int sd;

            if (i <= 2) 
            {
                sa = 1; sb = 1;
            }
            else 
            {
                fib(i - 2, out sc, out sd);
                sa = sc + sd;
                sb = sd + sa;
            }
            Console.Write(sa.ToString() + " " + sb.ToString() + " ");
        }
    }
}

Code:

#include <iostream>
using namespace std;

int niz[100] = { 0 };

int fib( int n )
{
    if( n == 0 ) return 0;
    else if( n == 1 ) return 1;
    else if( niz[n] > 0 ) return niz[n];
    else
    {
        //Memoizacija
        niz[n] = fib( n - 1 ) + fib( n - 2 );
        return niz[n];
    }
}

int main()
{
    int n; cin >> n;
    
    niz[0] = 0;
    niz[1] = 1;
    
    cout << fib( n ) << endl;
    return 0;
}

Code:
// O(n)
int fibonaci1(int n)
{
    int f2 = 1;    // f(0) = 1
    int f1 = 1;     // f(1) = 1
    int i;
    for(i=2; i<=n; i++)
    {
        f = f2 + f1;
        f2 = f1;
        f1 = f;
    }
    return f;
}
// O(1) - uslovno, ako zanemarimo slozenost funkcije pow
int fibonaci2(int n)
{
    float sqrt5 = pow(5, 0.5) / 0.5;    
    return (int) ((pow(0.5 + sqrt5, n) - pow(0.5 - sqrt5, n)) / (sqrt5 * 2.0));
}