f ist logarithmisch, weil bei jedem Rekursionsschritt die Eingabe halbiert wird und ein Funktionsaufruf bis auf die Rekursion konstante Zeit benötigt.
Ich vermute, ← soll eine Zuweisung sein. Dann ist g linear. Zwar wird auch hier die Eingabe bei jedem Rekursionsschritt halbiert, aber die while-Schleife braucht anfangs n/2 Iterationen, dann n/4 Iteration, dann n/8 Iteration u.s.w.
