- #1
pc2-brazil
- 205
- 3
Homework Statement
Analyze the worst-case time complexity of the following algorithm, which finds the first term of a sequence of integers equal to some previous term.
Code:
[B]procedure[/B] find (a[sub]1[/sub], a[sub]2[/sub], a[sub]3[/sub],..., a[sub]n[/sub]: integers)
location := 0
i := 2
[B]while[/B] i ≤ n and location = 0
[B]begin[/B]
j := 1
[B]while[/B] j < i and location = 0
[B]if[/B] a[sub]i[/sub] = a[sub]j[/sub] [B]then[/B] location := i
[B]else[/B] j := j + 1
i := i + 1
[B]end[/B]
2. The attempt at a solution
I will try to calculate the total number of comparisons needed. For a list of n integers, the worst-case complexity of the algorithm above is when there is no integer equal to some previous term (that is, when all integers are different). This is the case where the most comparisons will be needed.
I'm not sure about what's the best way to write this in a clear manner, but I will try to go from inside out (that is, first, the inner loop, and then the outer loop).
Inside the body of the outer loop, there is an inner while loop in order to compare the ith number with all the elements preceding it (that is, the elements from j = 1 to j = i - 1). That is, the inner loop is executed (i - 1) times, each of them comprising 3 comparisons -- 2 for entering the loop body (that is, j < i and location = 0) and 1 inside the loop body (to verify if ai = aj). There are still 2 more comparisons needed to verify that the loop terminated (that is, when j = i and location = 0). So, the total number of comparisons needed for this inner loop is 3(i - 1) + 2.
The outer while loop (which verifies if i ≤ n and location = 0) will be executed (n - 1) times, plus two comparisons for terminating the loop.
For each iteration of the outer loop, there will be 2 comparisons for entering the loop body (i ≤ n and location = 0), plus the number of comparisons done by the inner loop.
So, each iteration will need 2 comparisons (for entering the loop body) plus 3(i - 1) + 2; which gives 3(i - 1) + 4.
Thus, 3(i - 1) + 4 comparisons will be made n - 1 times with i = 2, ..., n, plus 2 more for terminating the outer loop. Then, the total number of comparisons done in the whole execution of the algorithm will be:
[tex]T(n)=2+\sum_{i=2}^{n}\left[3(i-1)+4 \right][/tex]
[tex]T(n)=2+\frac{1}{2}(3n^2+5n-8)[/tex]
Because T(n) is a polynomial of degree 2, its complexity is O(n²).
Tell me if I didn't make myself clear (I tried to be as clear as possible).
Thank you in advance.
Last edited: