Równanie cykliczne dla algorytmu sortowania - algorytm, rekurencja

Mam następujące pytanie dotyczące zadania domowego i nie jestem pewien, jak do niego podejść

Załóżmy, że mamy następujący algorytm sortowania:

Aby posortować tablicę o rozmiarze N (A [1… N]), algorytm wykona następujące czynności:

1. Rekurencyjnie, sortuj pierwsze elementy N-1 A [1… N-1]
2. Użyj wyszukiwania binarnego, aby znaleźć właściwe miejsce A [N], aby dodać je do posortowanej listy. Po znalezieniu właściwego miejsca, konieczne będzie przesunięcie wartości, aby zrobić miejsce dla A [N].

Napisz szczegółowe równanie powtarzalności tego algorytmu (nie pomijaj żadnych terminów).

Odpowiedzi:

gdzie C jest jakaś stała.

Zobaczmy, skąd każdy termin pochodzi z n > 1 walizka:

• T_ {n - 1}

Rekurencyjnie, sortuj pierwsze elementy N-1 A [1… N-1]

• log n

Użyj wyszukiwania binarnego, aby znaleźć właściwe miejsce A [N], aby dodać je do posortowana lista

• n

Po znalezieniu właściwego miejsca, konieczne będzie przesunięcie wartości, aby zrobić miejsce dla A [N].

Niech T (n) będzie czasem wykonywania algorytmuopisany dla tablicy n elementów. Po pierwsze, rekurencyjnie wywołuje się na pierwszych elementach n-1, dając nam koszt T (n-1). Następnie wykorzystuje wyszukiwanie binarne w celu znalezienia pozycji elementu w pierwotnej pozycji n, a tym samym biorąc czas log (n-1). Wreszcie przesuwa elementy (co najwyżej n-1), aby zrobić miejsce dla nowego, co wymaga co najwyżej n kroków.

Łącząc elementy, otrzymujemy T (n) <=T (n-1) + log (n-1) + n - 1. Wreszcie, ponieważ nie określiłeś przypadku bazowego, zakładam, że algorytm po prostu nie robi nic na pustej liście (a więc trywialnie go sortuje), a następnie pobiera T (0) = 0.