Federico,
Primero darte las gracias por la respuesta que me tenia a mal traer hace varios dias. Mi pregunta apuntaba justamente al razonamiento explicado en tu segunda respuesta. Tal y como tu lo mencionaste, pense en el peor caso como la suma de ambas ramas en el stack, pero es verdad que la funcion recursiva va hacia el paso base, por lo que sumar el costo de ambas ramas estaria mal.
Muchas gracias nuevamente.
Saludos.