zadania z informatyki - Analiza algorytmów

Prześledź działanie algorytmu 1 dla podanych poniżej wartości k i początkowych zawartości tablicy A. W każdym wierszu poniższej tabeli wpisz końcową zawartość tablicy A.

Rozważmy poniższy algorytm podobny do algorytmu 1.
Wejście:
k — liczba naturalna,
A[1...2^k] — tablica liczb całkowitych.
Algorytm 2:
n ← 1
dla i = 1,2,…,k wykonuj
n ← 2⋅n
s ← 1
dopóki s < n wykonuj
j ← 1
dopóki j < n wykonuj
(*) jeżeli A[j]>A[j+1]
zamień(A[j],A[j+1])
j ← j + 1
s ← s + 1
zwróć A[1], A[2],…,A[n]

Uwaga: Funkcja zamień(A[j],A[j+1]) zamienia miejscami wartości A[j] oraz A[j+1].
Uzupełnij luki w poniższych zdaniach. Przyjmij n = 2^k oraz k > 1.
Po zakończeniu działania algorytmu 2 element A[i] jest .........................
niż element A[i+1] dla każdego i większego od .........................
oraz mniejszego od .........................

Wiersz (*) algorytmu 2 wykonywany będzie w przebiegu algorytmu
• ..................................... niż n razy,
• ..................................... niż n² razy.