Laufzeitberechnung

Leiten Sie die Laufzeit/Kostenfunktion des folgenden Algorithmus für ein Array der Länge n>2 her.

• Gewertet werden nur Feldzugriffe.
• Überlegen Sie zunächst, für welche Eingaben jeweils der Best Case und der Worst Case eintritt.
• Gehen Sie bottom-up vor, d.h. berechnen Sie zunächst die Schritte der Funktion unicorn_ninja() in Abhängigkeit von pos. Betrachten Sie zunächst nur den Best Case.
• Berechnen Sie nun die Schritte für das Gesamtverfahren $a^{best}(n)$, indem Sie die Schritte der Schleifendurchläufe aufsummieren.
• Wiederholen Sie zuletzt die Herleitung für den Worst Case. Leiten Sie auch hier eine Formel für die Laufzeit $a^{worst}(n)$ her, diese müssen Sie aber nicht weiter vereinfachen.

# Gegeben: Ein Array a der Länge n>2.
pos = 0
result = 0
while pos<n:
    result += unicorn_ninja(a, pos, a[pos])
    pos += 1
return result

# Hilfsfunktion
function unicorn_ninja(a, pos, val):
    i = pos
    while i >= 0 and a[i] >= val:
        i -= 2
    return i