(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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.

(This pseudocode notation is the one used in "Discrete Mathematics and Its Applications" by Kenneth Rosen. The indentation indicates that a portion of code is the body of a loop structure. ":=" indicates attribution, while "=" indicates comparison. Tell me if any further clarification is needed.)Code (Text):[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 innerwhileloop in order to compare the i^{th}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 < iandlocation = 0) and 1 inside the loop body (to verify if a_{i}= a_{j}). 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.

Theouterwhile 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Analyzing the time complexity of an algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**