função algoritmo1()
0: inicio
1: se n = 0 então
2: retorne 0
3: senão
4: se n = 1 então
5: retorne 1
6: senão
7: retorne algoritmo1(n−1)+algoritmo1(n−2)
8: fim se
9: fim se
10:fim

função algortimo2(n)
0: inicio
1: se n = 0 então
2: retorne 0
3: senão
4: se n = 1 então
5: retorne 1
6: senão
7: penultimo = 0
8: ultimo =1
9: para i =2 até n faça
10: atual = penultimo + ultimo
11: penultimo = ultimo
12: ultimo = atual
13: fim para
14: retorne atual
15: fim se
16: fim se
17: fim

As complexidades dos algoritmo1 e algoritmo2 precedentes são, respectivamente, iguais a