dimanche 18 septembre 2016

Running Time of Algorithme - If statements inside While loop

I have this example

A = 2,1,8,4,3,6 // c1, n 
n = 6 // c2, n
i = 1 // c3, n
H = 2 // c4, n
inv = 0 // c5, n
while H <= n    // c6, n(n+1)/2-1               
    if A[i] > A[H] && !H = n // c7, n(n-1)/2
        inv = inv + 1
        H = H + 1 
    else if A[i] > A[H] && H = n // c10, n(n-1)/2
        inv = inv + 1
        i = i + 1
        H = i + 1
    else if A[i] < A[H] && !H = n // c14, n(n-1)/2
        H = H + 1
    else if A[i] < A[H] && H = n // c16, n(n-1)/2
        i = i + 1 
        H = i + 1
print inv // c19, n

My question to you fine gentlemen is how many n times will the code inside the if statement run in this example?

Aucun commentaire:

Enregistrer un commentaire