BubbleSort,Tiden för att exekvera

Algorithm bubblesort(A, n):
Input: An array A storing n integers.
Output: An array with the same integers in ascending order.
isReady = false
while not isReady
for i = 0 to n - 2
if A[i] > A[i+1] then
swap(A[i], A[i+1])
isReady = true
for i = 0 to n - 2
if A[i] > A[i+1] then
isReady = false



Någon som kan hjälpa? Ska räkna ut hur lång tid det tar för att exekvera algoritmen, bubblesort (( VÄRSTA FALLET ))
Det värsta fallet är om arrayen står t.ex [4,3,2,1]

Åh bubblesort är en algoritm som ska göra så att Arrayen blir sorterad med minsta värdet först osv.

Nån som kan hjälpa hur man ska räkna ut det värsta fallet, för ett givet n ?

Från wiki

"Bubble sort has worst-case and average complexity both О(n2)" (nästad for loop)

Man räknar aldrig komplexitet i tid. Din implemtation av Bubble sort vill ta olika tid att exikvera på din och min maskin.

duude... självklart ärre så. Men nu ska vi räkna på n.

Jag får ut värsta fallet som n(n-1) men som alla säger ska värsta fallet vara n^2

Säg att du sorterar 100000 tal. 100000(100000-1) jämfört med 100000*100000. Skillnaden är försumbar och man säger att den har n*n.

Edit: Tror jag

har suttit å diskuterat lite me classmates, å nu får vi fram att whileloopen körs n-1 gång

Sedan har vi två for loopar... varje loop körs n-1 gång.

2*(n-1)

Sedan körs whieloopen n-1 gång.. alltså blir det (n-1)*2(n-1) = 2(n-1)^2

Vilket är blir 2n^2... när n-> oo ( oändligheten ) ..

Vilket är O(n^2) då konstanter kan tas bort.

Komplexiteten i en algoritm beror inte på antal element "minus ett". Det har inget med gränsvärden att göra, komplexiteten är O(n^2) för alla n.

Linjär kod, tex, har komplexiteten konstant tid = O(1). Det blir inte O(2) bara för att koden är dubbelt så lång.

För övrigt körs loopen inte n-1 gånger om n=1.

KTH D11?