CODEWITHSUNDEEP
algorithmcomplexity-theorytime-complexitycalculus
HATEM EL-AZAB
HATEM EL-AZAB

Reputation: 371

complexity theory-sorting algorithm

I'am taking a course in complexity theory,and so it's need some mathematical background which i have a problem,. so while i'am trying to do some practicing i stuck in the bellow example

1)  for (i = 1; i < n; i++) {
2)      SmallPos = i;
3)      Smallest = Array[SmallPos];
4)      for (j = i+1; j <= n; j++)   
5)          if (Array[j] < Smallest) {
6)              SmallPos = j;
7)              Smallest = Array[SmallPos]  
            }   
8)       Array[SmallPos] = Array[i];
9)       Array[i] = Smallest;
    }

Thus, the total computing time is: 

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

and what i don't understand or confused about line 4 analyzed to n(n+1)/2 – 1, and line 5 3[n(n-1) / 2]. i knew that the sum of positive series is =n(first+last)/2 ,but when i tried to calculate it as i understand it it gives me different result. i calculate for line no 4 so it shoulb be =n((n-1)+2)/2 according to n(first+last)/2 ,but here it's n(n+1)/2 – 1. and same for 3[n(n-1) / 2].....i don't understand this too

also here's what is written in the analysis it could help if anyone can explain to me,

Statement 1 is executed n times (n - 1 + 1); statements 2, 3, 8, and 9 (each representing O(1) time) are executed n - 1 times each, once on each pass through the outer loop. On the first pass through this loop with i = 1, statement 4 is executed n times; statement 5 is executed n - 1 times, and assuming a worst case where the elements of the array are in descending order, statements 6 and 7 (each O(1) time) are executed n - 1 times.

On the second pass through the outer loop with i = 2, statement 4 is executed n - 1 times and statements 5, 6, and 7 are executed n - 2 times, etc. Thus, statement 4 is executed (n) + (n-1) +... + 2 times and statements 5, 6, and 7 are executed (n-1) + (n-2) + ... + 2 + 1 times. The first sum is equal to n(n+1)/2 - 1, and the second is equal to n(n-1)/2.

Thus, the total computing time is: 

T(n)    = (n) + 4(n-1) + n(n+1)/2 – 1 + 3[n(n-1) / 2]
        = n  + 4n - 4 + (n^2 + n)/2 – 1 + (3n^2 - 3n) / 2
        = 5n - 5 + (4n2 - 2n) / 2
        = 5n - 5 + 2n^2 - n
        = 2n^2 + 4n - 5 
        = O(n^2)

here's the link for the file containing this example: http://www.google.com.eg/url?sa=t&rct=j&q=Consider+the+sorting+algorithm+shown+below.++Find+the+number+of+instructions+executed+&source=web&cd=1&cad=rja&ved=0CB8QFjAA&url=http%3A%2F%2Fgcu.googlecode.com%2Ffiles%2FAnalysis%2520of%2520Algorithms%2520I.doc&ei=3H5wUNiOINDLswaO3ICYBQ&usg=AFQjCNEBqgrtQldfp6eqdfSY_EFKOe76yg

Upvotes: 0

Views: 433

Answers (1)

Origin
Origin

Reputation: 2017

line 4: as the analysis says, it is executed n+(n-1)+...+2 times. This is a sum of (n-1) terms. In the formula you use, n(first+last)/2, n represents the number of terms. If you apply the formula to your sequence of n-1 terms, then it should be (n-1)((n)+(2))/2=(n²+n-2)/2=n(n+1)/2-1.

line 5: the same formula can be used. As the analysis says, you have to calculate (n-1)+...+1. This is a sum of n-1 terms, with the first and last being n-1 and 1. The sum is given by (n-1)(n-1+1)/2. The factor 3 is from the 3 lines (5,6,7) that are each being done (n-1)(n)/2 times

Upvotes: 1

Related Questions