Witam. Byłabym wdzięczna jeśli ktoś by mi powiedział czy dobrze myślę, że ten algorytm ma złożoność O(n) i czy dobrym uzasadnieniem na to jest, że algorytm wykonuje stałą liczbę operacji dla każdej danej n bądź, że posiada jedną operację dominującą? Bo w zasadzie to nie wykonuje dla każdej danej stałej liczby operacji, bo w środku jeszcze jest if. Czy ma to jakieś znaczenie? Z góry dziękuję za pomoc!
A to algorytm:
void rozmieszczenie(int lewy, int prawy)
{
int i, j, piwot, temp;
i = (lewy + prawy) / 2;
piwot = tab[i];
tab[i] =tab[prawy];
j=lewy;
for(i = lewy; i < prawy; i++)
{
if(tab[i] < piwot)
{
temp =tab[i];
tab[i] =tab[j];
tab[j] = temp;
j++;
}
}
tab[prawy] =tab[j];
tab[j] = piwot;