Fibbonacci com Memoization - O(n)

O nome da técnica é Memoization... foi mal pessoal.

Boa dica, Daniel. É sempre importante saber que existem várias maneiras de se conseguir os mesmos resultados.
Alguns resultados são mais rápidos, outros mais seguros, outros conseguem ser tão rápidos quanto seguros, outros são melhor implementados em outra linguagem, e assim por diante.
Quem resolve dedicar-se a programação deve estar atento a técnicas específicas, e às características de cada linguagem, visando obter o melhor desempenho na resolução dos problemas.
As linguagens modernas tendem a trazer-nos uma certa acomodação mental, através do uso de módulos preconfigurados.
Nada de errado com isso; Porém se nos deixarmos acomodar, nosso raciocínio poderá ficar bastante bitolado, o que não é nada bom.

Interessante, mas me permita minha contribuição.

Complexidade é uma coisa legal. A serie de fibonacci aumenta o tempo de execução de acordo com o tamanho do elemento. No teu caso fizeste a serie de forma iterativa, ou seja, SEM RECURSÃO. recursividade é um LIXO para este tipo de coisa pois gasta muito tempo e pode ESTOURAR a pilha.

Mas tem uma forma MATEMÁTICA, com um ÚNICO PASSO que permite chegar a qualquer elemento da série (Algoritmos, Teoria e Prática, de Thomas H. Cormem).

A formula é meio esdrúxula e pode ter erro de precisão por conta dos doubles (raiz quadrada) mas FUNCIONA.
#include <stdio.h>
#include <math.h>
unsigned long int fibo(unsigned long int n)
{
long double s=sqrtl(5);
long double a1, a2;

if (n<=1){
return(n);
}

a1 = powl( (1+s)/2.0 ,n);
a2 = powl( (1-s)/2.0 ,n);

return ( (a1 - a2)/s + 0.5);
}

Só que neste caso, ao contrário do teu, o primeiro elemento é o posição 1 e não ZERO. Então o teu FIBO 40, aqui tem que ser passado 41:

elgio@didake:~/ulbra/Disciplinas/estrutura2/src> time ./fiboMAT 41
O elemento 41 da serie eh 165580141

real 0m0.003s
user 0m0.000s
sys 0m0.008s
elgio@didake:~/ulbra/Disciplinas/estrutura2/src>

MAIS UMA VEZ, saliento que por causa do uso de ponto flutuante e da perda de precisão, pode ter diferenças no resultado. Mas estamos falando de conceitos matemáticos, e tem uma forma de calcular qualquer elemento da série sem for ou recursividade (pois na matemática tu não precisas perder a precisão do raiz quadrada). Para melhorar muito, eu uso long double, que se estiver em um compilador de 64 bits será de 16 BYTES (128 bits) de tamanho :-O e um long int de 8 BYTES (64 bits).

Mas acredito (a ser testado) que em um simples compilador de 32 bits não se perderá precisão para elementos pequenos (no meu, o processo matemático perde precisão no 85):

elgio@didake:~/ulbra/Disciplinas/estrutura2/src> for A in `seq 81 90`; do ./fiboMAT $A; ./fiboIT $A;echo ;done
O elemento 81 da serie eh 37889062373143906
O elemento 81 da serie eh 37889062373143906

O elemento 82 da serie eh 61305790721611591
O elemento 82 da serie eh 61305790721611591

O elemento 83 da serie eh 99194853094755497
O elemento 83 da serie eh 99194853094755497

O elemento 84 da serie eh 160500643816367088
O elemento 84 da serie eh 160500643816367088

O elemento 85 da serie eh 259695496911122586
O elemento 85 da serie eh 259695496911122585

O elemento 86 da serie eh 420196140727489674
O elemento 86 da serie eh 420196140727489673

O elemento 87 da serie eh 679891637638612260
O elemento 87 da serie eh 679891637638612258

O elemento 88 da serie eh 1100087778366101934
O elemento 88 da serie eh 1100087778366101931

O elemento 89 da serie eh 1779979416004714193
O elemento 89 da serie eh 1779979416004714189

O elemento 90 da serie eh 2880067194370816127
O elemento 90 da serie eh 2880067194370816120

Outra contribuição.

Eu mudaria de:

#define MAX 512
int v[MAX];

int fibonacci(int n)
{
if (n < 2)
return 1;
...

Para:
#define MAX 512

int fibonacci(int n)
{
static int v[MAX];

if (n < 2)
return 1;
...

MOTIVO: variáveis globais não é nada legal de ser usado!! Efeito colateral.

caramba..... interessante esse método direto...

obrigado!