Orden de algun algoritm

[ElPatoGarrido]

Hola, he estado aprendiendo las cosas basicas de programacion en C/C++, Pascal, etc... pero encuentro que hay algo que me cuesta mas y es la de ver el orden de un algoritmo, no de uno sencillo (si tampoco es tan dificil), pero por ejemplo si tengo el algoritmo para calcular la suecuencia de fibonacci de forma recursiva (y quiero calcular el orden de ese algoritmo) simplemente se me ocurre decir que es de O(n^2) por que fibonacci de n llamara recursivamente a la misma funcion 2 veces, despues estas 2 a otras 2, y asi sucesivamente lo que hara que se aproxime a 2^n, pero si me pidieran hacerlo de la forma matematica, o si me lo preguntaran en una prueba, no sabria como justificarlo, e imaginense si veo una funcion que se llama a si misma o a otras funciones por el argumento partido a la mitad etc... etc... etc... No tendria ni reverenda idea como calcular el orden de un algoritmo en casos mas complejos.

¿Alguien ha tenido el mismo problema, que puedo hacer?

Esa seria mi pregunta, gracias.