PAA/part-1/2018.tex

%! TEX root = ../main.tex

\section{Zerówka 2018}
\task Dla programu poniżej:
\begin{algorithm}[H]
    \caption{Program do przanalizowania}
    \begin{algorithmic}[1]
        \For{$i = 1 \ldots n^2$} \label{prog:1-2018:to-n2}
            \For{$j = i \ldots n$} \label{prog:1-2018:to-n}
                \State $k \gets 1$
                \While{$k < n$}
                    \State $k \gets k + k$ \label{prog:1-2018:1-basic}
                \EndWhile
            \EndFor
        \EndFor
    \end{algorithmic}
\end{algorithm}
\noindent Wybierz najlepsze możliwe oszacowanie liczby kroków spośród:

\vspace{.3cm}
$n^4$ \quad $n^3 \log_2 n$ \quad $n^3$ \quad $n^2 \log_2 n$ \quad $n^2 \log_2 \sqrt n$ \quad $n^2$
\vspace{.2cm}

\begin{solution}
    Bez dokładnego przeanalizowania programu łatwo zauważyć, że mamy dwie pętle, jedną ograniczoną przez $n^2$ w linii 
    \ref{prog:1-2018:to-n2}, oraz jedną ograniczoną przez $n$ w linii \ref{prog:1-2018:to-n}. $n^3$ jednak nie jest
    poprawną odpowiedzią, zauważmy że w linii \ref{prog:1-2018:to-n} iteracja zaczyna się od $i$ a nie od $1$. Zatem
    jeżeli $i > n$ to pętla w ogóle się nie wykona. Musimy zatem rozbić analizę programu na dwa osobne przedziały:
    
    \begin{column}{.5}
        \begin{equation} \label{eqn:1-2018:1-n}
            i = 1 \ldots n
        \end{equation}
    \end{column}
    \begin{column}{.5}
        \begin{equation} \label{eqn:1-2018:n-n2}
            i = n \ldots n^2
        \end{equation}
    \end{column}

    Jak zauważyliśmy, w przedziale $n \ldots n^2$ pętla z linii \ref{prog:1-2018:to-n} w ogóle się nie wykona. Zatem
    za operację podstawową przyjmiemy iterację najbardziej zewnętrznej pętli. Pętla ta wykona się $n^2 - n$ razy.
    
    \begin{equation}\label{eqn:1-2018:1:T1}
        T_1 = n^2 - n 
    \end{equation}

    W przypadku \ref{eqn:1-2018:1-n}, jako operację podstawową musimy przyjąć jednak najbardziej wewnętrzną operację, 
    czyli linię \ref{prog:1-2018:1-basic}. Ponieważ $k \gets k+k$ jest tym samym co $k \gets 2k$ to wiemy, że z
    każdą iteracją pętli \textbf{while} k rośnie wykładniczo. 
    
    \begin{equation*}
        k = 1,\ 2,\ 4,\ 8,\ 16,\ 32,\ \ldots
    \end{equation*}

    Zakładając, że $l$ to liczba wykonań pętli możemy zapisać:
    \begin{equation}
        k = 2^l
    \end{equation}

    Czyli warunek $k < n$ przestanie być spełnionym gdy
    \begin{equation*}
        2^l \geq n \iff l \geq \log_2 n
    \end{equation*}

    Skąd możemy wywnioskować, że maksymalna liczba wykonań pętli wynosi
    \begin{equation}
        l_{\text{max}} = \log_2 n
    \end{equation}
    
    Zgodnie z tym, co ustaliliśmy we wprowadzeniu, czas w którym ten program będzie się wykonywał możemy zaprezentować 
    w formie sumy takiej jak poniżej:
    \begin{align*}
        T_2 &= \sum_{i=1}^n \sum_{j=i}^n \sum_{k=1}^{\log_2 n} 1 = \sum_{i=1}^n \sum_{j=i}^n \log_2 n 
             = (\log_2 n)\sum_{i=1}^n \sum_{j=i}^n 1 \\
            &= (\log_2 n)\sum_{i=1}^n (n - i + 1) = (\log_2 n)\cdot\left(\sum_{i=1}^n n - \sum_{i=1}^n i + \sum_{i=1}^n 1\right)  \\
            &= (\log_2 n)\cdot\left(n^2 - \frac{n(n+1)}{2} + n\right) = (\log_2 n)\cdot\left(n^2 - \frac{1}{2}n^2 - \frac{1}{2}n + n\right) \\
            &= (\log_2 n)\cdot\left(\frac{1}{2}n^2 -\frac{1}{2}n\right) = \frac{1}{2}n^2\log_2n + \frac{1}{2}n^2\log_2n  \\
    \end{align*}

    ponieważ $a\log_c b = \log_c b^a$ uzyskujemy
    \begin{equation}\label{eqn:1-2018:1:T2}
        T_2 = n^2\log_2 \sqrt n + n\log_2 \sqrt n
    \end{equation}

    Łącząc czas $T_2$ z \refeq{eqn:1-2018:1:T2} czasem $T_1$ z \refeq{eqn:1-2018:1:T1}, uzyskujemy łącznie:
    \begin{equation}
        T = T_1 + T_2 = n^2\log_2 \sqrt n + n^2 + n\log_2 \sqrt n  - n 
    \end{equation}

    Ponieważ szacujemy czas, interesuje nas głównie składnik najbardziej rzutujący na czas - w typ wypadku jest to
    $n^2\log_2\sqrt n$.
\end{solution}

\task Graf kubiczny (tj. $3$-regularny) $G$ zapisano w postaci macierzy sąsiedztwa wierzchołków. Napisz program, który 
zwraca liczbę diamentów (tj. $K_4 - e$) w grafie $G$, uzasadnij jego poprawność oraz złożoność obliczeniową. 
\tip{Czy $G$ może mieć 2 sklejone ze sobą diamenty?}

\begin{solution}
    Zadanie definiuje diament jako $K_4 - e$ - graf pełny o 4 wierzchołkach, pozbawiony jednej krawędzi. spróbujmy 
    jakoś scharakteryzować ten graf.

    \begin{figure}[H]
        \centering
        \begin{tikzpicture}
            \foreach \pos[count=\i] in{(0,1),(1,0),(0,-1),(-1,0)} \node[vertex] (\i) at \pos {\i};
            \foreach \u/\v in {1/2,1/3,1/4,2/3,4/3} \draw[thick] (\v) edge (\u);
        \end{tikzpicture}
        \caption{diament}
    \end{figure}

    Graf ten posiada 4 wierzchołki, z czego 2 stopnia conajmniej 3 (połączone z pozostałymi, wchodzącymi w skład 
    diamentu) - na rysunku wyżej są to wierzchołki 1 i 3, a 2 stopnia conajmniej 2 - oba połączone z tymi stopnia 
    conajmniej 3 - na rysunku są to wierzchołki 4 oraz 2.

    Możemy też zauważyć, że z wierzchołka 1 do 3 można dojść 3 ścieżkami, jedną o długości 1, oraz dwiema długosci 2 
    (poprzez wierzchołki 4 i 2).

    Dla grafu przedstawionego w formie macierzy sąsiedztwa $A$, $n$-ta potęgę macierzy $A$ możemy interpretowac jako
    liczbę ścieżek długości $n$ między danymi wierzchołkami - z uwagi na powyższe, ten fakt będzie nam bardzo pomocny.
    Macierz można podnieść do potęgi wykorzystując szybki algorytm mnożenia macierzy, działający w czasie
    $O(n^{2.374})$, mając taką macierz wystarczy tylko przejść po wszystkich wierzchołkach i sprawdzić czy do dowolnego
    sąsiada jesteśmy w stanie znaleźć dokładnie jedną ścieżkę długości 1 i 2 ścieżki długości 2. 

    W takim rozważaniu musimy jednak uwzględnić, że każdy z diamentów zostanie policzony dokładnie 2 razy, ponieważ 
    policzymy zarówno wierzchołki $1$ jak i $3$. Wynik uzyskany z procedury musimy z tego powodu podzielić przez 2.

    \begin{algorithm}[H]
        \caption{algorytm rozwiązujący problem}
        \begin{algorithmic}[1]
            \State $A_2 \gets A^2$ \Comment{$O(2.374)$}
            \State $c \gets 0$

            \ForAll{$v \in V(G)$} \Comment{$\Theta(n)$}
                \ForAll{$u$ sąsiadujący z $v$} \Comment{$\Theta(n)$}
                    \If{$A_2[v, u] \geq 2 \land A[v, u] = 1$} \Comment{$\Theta(1)$}
                        \State $c \gets c + 1$ \Comment{$\Theta(1)$}
                    \EndIf
                \EndFor
            \EndFor

            \State \Return $\frac{1}{2}c$
        \end{algorithmic}
    \end{algorithm}

    Złożoność pętli to zatem $\Theta(n^2)$, jednak ponieważ czas potrzebny na podniesienie macierzy do potęgi ma 
    złożoność $O(n^{2.374})$, to podniesienie do potęgi ma większy narzut czasowy niż pętla, zatem złożoność naszej
    procedury ostatecznie jest równa złożoności podnoszenia macierzy do kwadratu.
\end{solution}

\task Problem znajdowania drogi długości $k$ w nieobciążonym grafie $n$-wierzchołkowym ma następujące algorytmy.
\begin{itemize}
    \item Monien (1989)
    \item Alon i in. (1994)
    \item Kneis i in. (2006)
    \item Koutis (2008)
    \item Williams (2009)
    \item Bj\"orklund (2010)
    \item Bj\"orklund i in. (2010)
\end{itemize}

Przypisz im odpowiednie złożoności spośród: $O(4^kn^{O(1)})$, $O(k!n^{O(1)})$, $O(1.66^kn^{O(1)})$, $O((2e)^kn^{O(1)})$, $O((2^k)n^{O(1)})$, $O(2^{\frac{3k}{2}}n^{O(1)})$, $O(1.66^nn^{O(1)})$

\begin{solution}
    Na całe szczęście zadanie nie wymaga od nas pamiętania kiedy jaki algorytm powstał - ciężko byłoby to nawet znaleźc.
    Spokojnie jednak można założyć, że żaden autor nie bedzie chwalił się tym, że napisał gorszy algorytm - wystarczy
    zatem posortowac te algorytmy od najwolniejszego do najszybszego.
 
    Szczęśliwie wszystkie podane złożoności są wykładnicze - za wyjątkiem jednej zawierającej $k!$. Wiadomo, że silnia
    rośnie szybciej od każdej możliwej funkcji wykłaniczej, zatem pierwszemu algorytmowi przypiszemy złożoność $O(k!n^{O(1)})$
    
    Zastanawiać może jeszcze obecność $n^{O(1)}$ - wyrażenie to w zasadzie oznacza, że mamy doczynienia z jakimś 
    wielomianem o nieznym największym wykładniku. Wykładnik ten jest jednak stały i niezależny od $n$ - stąd $O(1)$.
    Ponieważ wszystkie funkcje mają różne podstawi lub wykładniki to spokojnie możemy pominąć ten kawałek w dalszych
    rozważaniach.

    Zostało nam więc uszeregować pozostałe funkcje, na ten moment nie są one jednak przedstawione w formie, która 
    umożliwiłaby łatwe porównanie. Przedstawmy wszystkie złożoności tak, aby w podstawie była jakaś liczba (a 
    przynajmiej jej przybliżona wartość):

    \begin{table}[H]
        \centering
        \begin{tabular}{ll}
            \textbf{złożoność} & \textbf{złożoność znormalizowana} \\\hline
            $O(4^k)$ & $O(4^k)$ \\ 
            $O(1.66^k)$ & $O(1.66^k)$ \\ 
            $O((2e)^k)$ & $O(5.44^k)$ \\ 
            $O(2^k)$ & $O(2^k)$ \\ 
            $O(2^\frac{3k}{2})$ & $O(2.83^k)$ \\ 
            $O(1.66^n)$ & $O(1.66^n)$
        \end{tabular}
    \end{table}

    Dla funkcji wykładniczych o różnych podstawach, szybciej rośnie zawsze funkcja o większej podstawie, tzn. mając 
    przykładowe funkcje
    \begin{align}
        f(n) = 2^n && g(n) = 3^n
    \end{align}

    wiemy, że $f = o(g)$, czyli $f$ rośnie zdecydowanie wolniej od $g$. To pozwala uszeregować nam większość złożoności:
    $O((2e)^kn^{O(1)}), O(4^kn^{O(1)}), O(2^\frac{3k}{2}n^{O(1)}), O(2^kn^{O(1)})$. Pozostały nam jeszcze dwie:
    $O(1.66^nn^{O(1)}), O(1.66^kn^{O(1)})$.

    Obie te funkcje mają jednakową podstawę potęgi jednak różne wykładniki: $k$ i $n$, co wiemy o relacji między tymi 
    dwoma wartościami? W grafie $n$ wierzchołkowym najdłuśza droga będzie miała długość $n$ - i będzie to cykl hamiltona.
    Z tego wynika, że
    \begin{equation}
        k \leq n
    \end{equation}

    Stąd wniosek, że poprawną kolejnością będzie $O(1.66^nn^{O(1)}), O(1.66^kn^{O(1)})$. Podsumowując:
    \begin{table}[H]
        \centering
        \begin{tabular}{lrl}
            \textbf{autor} & \textbf{rok} & \textbf{złożoność} \\\hline
            Monien & 1989 & $O(k!n^{O(1)})$ \\
            Alon i in. & 1994 & $O((2e)^kn^{O(1)})$ \\
            Kneis i in. & 2006 & $O(4^kn^{O(1)})$ \\
            Koutis & 2008 & $O(2^\frac{3k}{2}n^{O(1)})$ \\
            Williams & 2009 & $O(2^kn^{O(1)})$ \\
            Bj\"orklund & 2010 & $O(1.66^nn^{O(1)})$ \\
            Bj\"orklund i in. & 2010 & $O(1.66^kn^{O(1)})$ \\
        \end{tabular}
    \end{table}
\end{solution}

\task W pewnym systemie informacyjnym chcemy mieć bazę danych, która w czasie stałym - $O(1)$ - będzie odpowiadała na
pytania, jaka jest odległość między dwoma węzłamu $u, b \in V$, grafu $G = (V, E)$ gdzie $|V| = n$. Zaprojektuj 
taką strukturę danych i oszacuj jako funkcję $n$ jej złożoność pamięciową i złożoność czasową jej budowania.
\tip{Zastosuj algorytm Dijkstry}

\begin{solution}
    Potrzebujemy, aby dostęp do danych był w czasie $O(1)$ - czyli wszystkie potrzebne dane musimy już mieć wygenerowane.
    Połączenia możemy zapisac w postaci macierzy sąsiedztwa, a macierz sąsiedztwa $n$ wierzchołków zajmuje $\Theta(n^2)$ 
    bajtów. 

    Jeżeli chodzi o złożoność budowania tej struktury, to korzystamy z podpowiedzi. Musimy przeliczyć odległości między
    wszystkimi parami wierzchołków. Jak wiemy, par tych jest $O(n^2)$. Z podpowiedzi wiemy, że powinniśmy zastosować
    algorytm Dijkstry, jego złożoność wynosi $O(m\log n)$ - i te informacje trzeba było chyba znaleźć w jakiejś książce.

    Algorytm Dijkstry nie tylko wyznacza odległość pomiędzy dwoma wierzchołkami, ale w zasadzie odległości z danego
    wierzchołka do wszystkich wierzchołków. Wszystkich wierzchołków jest $n$ i dla każdego musimy wykonać algorytm
    dijkstry, co ostatecznie daje nam złożoność $O(nm\log n)$. \textit{Tej odpowiedzi nie jestem pewien.}
\end{solution}

\task Dana jest procedura:
\begin{algorithm}[H]
    \caption{Program do zbadania}
    \begin{algorithmic}
        \Function{zagadka}{$n$} \funclabel{proc:1-2018:zagadka}
            \For{$i = 1 \ldots 2n^2$}\EndFor
            \Statex
            \If{$n \leq 2$}
                \State \Return 1
            \Else
                \State \Return $8 \cdot $\Call{zagadka}{$\floor{\frac{n}{2}}$}$ - $\Call{zagadka}{$\floor{\frac{n}{4}}$} 
            \EndIf
        \EndFunction
    \end{algorithmic}
\end{algorithm}

\subtask Oszacuj od dołu liczbę kroków wykonanych przez procedurę \ref{proc:1-2018:zagadka}
\subtask Oszacuj od góry liczbę kroków wykonanych przez procedurę \ref{proc:1-2018:zagadka}
\subtask Oszacuj złożoność obliczeniową procedury \ref{proc:1-2018:zagadka}
\subtask Oszacuj od dołu tempo wzrostu funkcji \ref{proc:1-2018:zagadka}
\subtask Oszacuj od góry tempo wzrostu funkcji \ref{proc:1-2018:zagadka}
\subtask Złożoność procedury \ref{proc:1-2018:zagadka} jest: subliniowa, liniowa, kwadratowa, subwykładnicza, wykładnicza, superwykładnicza

\begin{solution}
    Liczbę kroków wykonanych przez te funkcję oznaczmy przez $L$. Pamiętając, że każde wywołanie funkcji kosztuje czas
    możemy ułożyć równanie wyrażające liczbę kroków.

    \begin{equation}
        L(n) = \begin{cases}
            n^2 & \text{dla } n \leq 2 \\ 
            L\left(\floor*{\frac{n}{2}}\right) + L\left(\floor*{\frac{n}{4}}\right) + n^2 & \text{dla } n > 2 
        \end{cases}
    \end{equation}

    Ponieważ funkcję rozważamy generalnie dla dużych $n$ to możemy spokojnie pominąć pierwszy przypadek i skupić się
    tylko na tym pierwszym. Dla tego typu funkcji nie mamy żadnego twierdzenia pozwalajacego oszacowac ją dokładnie. 
    Musimy zatem oszacować ją z góry i z dołu. Aby tego dokonac, zauważmy, że liczba kroków na ogół jest funkcją rosnącą
    względem argumentu - ciężko wyobrazić sobie algorytm, który dla mniejszej ilości danych musiałby wykonywac mniej 
    operacji. 

    Zatem dla każdego $a > b$ zachodzi $L(a) > L(b)$. Bez wątpienia, $\frac{n}{2} > \frac{n}{4}$, co za tym idzie
    \begin{equation}
        L\left(\floor*{\frac{n}{2}}\right) > L\left(\floor*{\frac{n}{4}}\right)
    \end{equation}

    Zatem jeżeli zastąpimy $L(\floor{\frac{n}{4}})$ przez $L(\floor{\frac{n}{2}})$ na pewno uzyskamy większą wartość.
    \begin{equation}
        L(n) = L\left(\floor*{\frac{n}{2}}\right) + L\left(\floor*{\frac{n}{4}}\right) + n^2 < 2L\left(\floor*{\frac{n}{2}}\right) + n^2
    \end{equation}

    Tego typu funkcję jesteśmy już w stanie oszacować zgodnie z zależnością dla funkcji typu ,,dziel i zwyciężaj'':

    \begin{equation*}
        T(n) = aT\left(\floor*{\frac{n}{b}}\right) + d(n)
    \end{equation*}
    \begin{equation}\label{eqn:1:divide-and-conquer}
        T(n) = \begin{cases}
            \Theta(n^{\log_b d(b)}) & d(b) > a \\
            \Theta(n^{\log_b a}\log n) & a = d(b) \\
            \Theta(n^{\log_b a})    & a > d(b) \\
        \end{cases}
    \end{equation}

    W tym wypadku $a = 2$, $b = 2$, $d(n) = n^2, d(b) = 4$ czyli przypadek 1, złożoność wynosi $\Theta(n^{\log_2 4}) = \Theta(n^2)$.
    Jednak pamiętajmy, że w tym wypadku rozpatrywaliśmy ograniczenie górne, zatem nasza pierwotna funkcja jest
    asymptotycznie ograniczona z góry, a złożoność to ostatecznie $O(n^2)$.

    Szacując od dołu musimy znaleźć jakąś funkcję, która zawsze będzie mniejsza. Ponieważ mamy same dodawania liczb
    dodatnich to wystarczy, że pozbędziemy się jednego - preferowalnie tego mniejszego - składnika, w tym wypadku
    w ogóle opuścimy rozważanie $L(\floor*{\frac{n}{4}})$.
    \begin{equation}
        L(n) = L\left(\floor*{\frac{n}{2}}\right) + L\left(\floor*{\frac{n}{4}}\right) + n^2 > L\left(\floor*{\frac{n}{2}}\right) + n^2\
    \end{equation}

    W tym wypadku stosując analogiczne rozumowanie do ograniczenia z góry otrzymamy ograniczenie dolne $\Omega(n^2)$.
    Ponieważ liczba jest jednocześnie $O(n^2)$ oraz $\Omega(n^2)$ to możemy powiedziec, że jest to $\Theta(n^2)$.

    W złożoności obliczeniowej uwzględniamy wzrost względem rozmiaru danych, a nie konkretnych danych. W wypadku liczb
    rozmiarem danych jest liczba bitów potrzebna do zapisania liczby. Przykładowo dla rozmiaru $n = 5$, maksymalna liczba
    która odpowiada temu rozmiarowi to $2^5 = 32$. Licząc złożoność takich procedur za każde $n$ podstawiamy $2^n$, 
    czyli złożoność procedury to $\Theta((2^n)^2)$ czyli $\Theta(4^n)$.

    Wartości zwracane przez funkcję można opisac za pomocą poniższego równania:
    \begin{equation}
        \proc{zagadka}(n) = \begin{cases}
            1 & \text{dla } n \leq 2 \\
            8\cdot\proc{zagadka}(\floor*{\frac{n}{2}}) - \proc{zagadka}(\floor*{\frac{n}{4}}) & \text{dla } n > 2
        \end{cases}
    \end{equation}

    Policzmy kilka kolejnych wartości funkcji, aby wiedzieć z czym mniej wiecej mamy doczynienia:
    \begin{table}[H]
        \centering
        \begin{tabular}{l|rrrrrrrrrr}
            $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline
            $\proc{zagadka}(n)$ & 1 & 1 & 7 & 7 & 55 & 55 & 55 & 55 & 433 & 433 \\
        \end{tabular}
    \end{table}

    Jak widać funkcja ta jest funkcją rosnącą, zatem możemy wynioskować że dla $a > b$ zachodzi 
    $\proc{zagadka}(a) \geq \proc{zagadka}(b)$. Aby ograniczyć funkcję z góry, pozbędziemy się 
    mniejszego z czynników doodawaniu: $\proc{zagadka}(\floor*{\frac{n}{4}})$:
    \begin{equation}
        8\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) 
        \geq 8\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) - \proc{zagadka}\left(\floor*{\frac{n}{4}}\right)
    \end{equation}

    Taką postać jesteśmy w stanie łatwo oszacować z zależności dziel i rządź: $a = 8$ $b = 2$ $d(n) = 0$. Ostatecznie
    uzyskujemy, że $\proc{zagadka}(n) = O(n^{\log_2}{8}) = O(n^3)$. Szacując z góry, zamieniamy mniejszy czynnik na
    większy zatem $\proc{zagadka}(\floor*{\frac{n}{4}})$ zamieniamy na $\proc{zagadka}(\floor*{\frac{n}{2}})$, uzyskując:
    \begin{equation*}
        8\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) - \proc{zagadka}\left(\floor*{\frac{n}{2}}\right) = 7\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) 
    \end{equation*}
    \begin{equation}
        7\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) 
        \leq 8\cdot\proc{zagadka}\left(\floor*{\frac{n}{2}}\right) - \proc{zagadka}\left(\floor*{\frac{n}{4}}\right)
    \end{equation}

    Szacując analogicznie otrzymamy ograniczenie z dołu $\Omega(n^{\log_2 7})$.
\end{solution}

\task Procedura szybkiego sortowania tablicy wywoływana jako \ref{proc:1-2018:quicksort}, zdefiniowana jest następująco:
\begin{algorithm}[H]
    \caption{Definicja funkcji \ref{proc:1-2018:quicksort}}
    \begin{algorithmic}
        \Function{QuickSort}{$l, r$}\funclabel{proc:1-2018:quicksort}
            \If{$l < r$}
                \State $i \gets~$\Call{PodzielTablicę}{$l, r$}\Comment{kosztem $\leq n$ operacji podziel fragmenty tablicy}
                \State \Call{QuickSort}{$l, i-1$} \Comment{posortuj lewą część}
                \State \Call{QuickSort}{$i, r$} \Comment{posortuj prawą część}
            \EndIf
        \EndFunction
    \end{algorithmic}
\end{algorithm}

\subtask Rozważ optymistyczną liczbę kroków, tj. gdy za każdym razem wybieramy medianę sortowanego fragmentu tablicy. 
Ułóż odpowiednie równanie rekurencyjne, a następnie podaj jego rozwiązanie asymptotyczne.
\subtask Rozważ pesymistyczną liczbę kroków, tj. gdy za każdym razem wybieramy element najmniejszy w sortowanym 
fragmencie tablicy. Ułóż odpowiednie równanie rekurencyjne, a następnie podaj jego rozwiązanie asymptotyczne.