Здравейте. Имам да намеря сложността на алгоритъма за сортиране(метод на мехурчето) на масиви:

for i:=1 to n-1 do
 for j:=2 to n+1-i do
   if a[j-1]>a[j] then
    begin
	 elem:=a[j-1];
	 a[j-1]:=a[j]:
	 a[j]:=elem;
    end;

Така и аз уж започнах да пиша нещо. Значи на If и полаганията сложността е О(1), тъй че не се занимавам с тях. После в циклите е по-сложно. Тъй като е вложение на цикли почвам от вътрешния. Посредством сбор на аритмерична прогресия, намирам че броя на итерациите на вътрешния цикъл е n(n-1)/2 . На външния съответно е n-1 и за сложността умножавам броя на итерациите на вътрешния по броя на външния:

(n(n-1)(n-1))/2. И ми се получава това, а в интернет е дадено като О(n^2) ... Къде бъркам ?

Благодаря предварително!

Посредством сбор на аритмерична прогресия, намирам че броя на итерациите на вътрешния цикъл е n(n-1)/2 . На външния съответно е n-1 и за сложността умножавам броя на итерациите на вътрешния по броя на външния:

(n(n-1)(n-1))/2. И ми се получава това, а в интернет е дадено като О(n^2) ... Къде бъркам ?

Грешна ти е логиката. Значи много хубаво за сбора на аритметична прогресия, обаче забравяш че тази сметка включва и външния цикъл. Така че сложността си е точно n(n-1)/2...