Как определить сложность алгоритма?

Question

[asault_ceko]

Наткнулся на такой алгоритм сортировки. Это микс выбора и обмена. Мне интересно узнать, какая у него сложность. Я уже нашел K1 и K2 и думаю, что здесь будет O(n^3), но не уверен, потому что может здесь O(n^2)? Просто дальше трудно и не могу уже придумать зависимость.

K1 = [n/2]; 
K2 = [(n^2)/4];

Comments

[hint000]

может здесь O(n^2)

Так и есть, O(n^2). Неоткуда взяться O(n^3). K1 и K2 складываются, а не умножаются.

Answer 1

[Дмитрий Перевозкин]

Может эта статья вам поможет

Answer 2

[Wataru]

Внутренние циклы выполняют суммарно максимум 8(r-l-1) операций. На каждой итерации внешнего цикла r-l уменьшается на 2. Т.е. всего операций будет 8(n-2)+8(n-4)+8(n-6)...

Можете эту арифметическую прогрессию подсчитать и оценить?

Answer 3

[Mercury13]

У нас два вложенных цикла, каждый порядка n.
Значит, O(n)·O(n) = O(n²), если не докажем меньше.
Не докажем, там обычная арифметическая прогрессия, которая что-то вроде n(n—1)/2.