Berechnung von Big-O für mehrere rekursive Anrufe, bei denen einer logn und der andere linear ist ⇐ Python

[Guest]

def f(n):
   if n
Ich habe dieses Problem in meiner Algorithmenklasse. Nach meinem Verständnis sollte es exponentiell sein. An jedem Zweig des Baumes sollten Sie zwei Anrufe haben, sodass es exponentiell ist. Das F (n // 2) trägt nichts zur Komplexität bei, da es dominiert wird.
Die Optionen, die mir angegeben wurden br /> o (logn)^2 < /li>
o (nLogn) < /li>
o (n (logn)^2) < /li >
o (n^2) < /li>
< /ul>
Keine von ihnen macht mich für diesen Kontext Sinn. < /p>