Es un tema un tanto complicado para explicarlo así pero haré lo que pueda.
Cuando hablas de complejidad n la n se refiere a los n datos que le das al algoritmo, entonces por ejemplo un for:
Código:
ejemplo = "ejemplo"
for (char c : ejemplo){
print c;
}
por cada dato (cada char en "ejemplo") se hace una operacion, si se agraga un char ("ejemplo1"), se agrega una operación. En cambió si es un doble for:
Código:
ejemplo = "ejemplo"
for (char c : ejemplo){
for (char b : ejemplo){
print c+b;
}
}
Ahí si agregar un char ("ejemplo1") realmente agregaste n operaciones mas, porque ahora el for de adentro se hara tambien para el char "1".
Para poder hacer este análisis de complejidad se suele hacer un procedimiento que consiste en sumar una constante A a cada operacion. Los ciclos se tratan como sumas (sumatorias) y pues la recursión es otra cosa que no podría explicar aquí.
Sé que quieres la explicación sobre el caso recursivo de fibonacci pero espero que esto te ayude un poco.