Berechne doch mal die ersten paar Terme: 1,3,7,15,31,... Fällt dir bei denen ein Muster auf? (Tipp: Addiere immer 1) Wenn du das Muster erkannt hast, kannst du dieses mit vollständiger Induktion zeigen. Alternativ gibt es bestimmt irgendein Mastertheorem, das diesen Fall abdeckt, aber ich kann mir die nicht alle merken.
Schon bevor du den genauen Aufwand berechnet hast, solltest du erkennen, dass sich der Aufwand bei jedem Schritt ungefähr verdoppelt, also solltest du etwas in \(\mathcal O(2^n)\) erwarten.