анализ сложности сортировки пузыря

Question

Возможно, этот вопрос задан несколько раз, но у меня есть сомнения. В следующем алгоритме:

BubbleSort(v[n]) 
i←0 
exchange←V 
while (exchange) 
    exchange←F 
    i←i+1 
    for pos=0 to n-i 
     if v[pos]>v[pos+1] then 
      swap(v[pos],v[pos+1]) 
      exchange←V 
     endif 
    endfor 
endwhile 

Я проанализировал это следующим образом:

, но у меня есть сомнения, если я сделал правильно, потому что если я анализирую внутренний цикл я могу сказать, что у меня есть:

, где можно сказать, что с зависит от величины внешнего контура в то время, потому что он может быть активным или нет, какой анализ является более точным из тех, которые я изложил здесь?

Thanks

Answer 1

Оба ваших анализа ошибочны.

В вашем первом анализе, когда вы устраняете внешнюю сумму, вы обрабатываете выражение внутри суммы, как если бы оно не зависело от переменной суммирования, если это не так. Ваша работа после этого имеет i в ней даже после того, как исключена сумма, определяющая i, ясный признак того, что вы сделали что-то неправильно.

Во втором анализе вы забываете про c после ....