Simple Algorithm time complexity Question

Question

Hi, I am working on an assignment for an intro Datamining course. I am trying to figure out the time complexity of an algorithm (see below)? Is it linear/exponential/log/quadratic/polynominal? Any tips on how to approach a question like this would be much appreciated

Consider the following algorithm for finding the third smallest element in an array:

• Input: n, a[1..n] - array a of numbers, and n is its size, n>=3
• Output: - return 3rd smallest number
• Temporary variables: b[1..3], t, i

Code:

b[1] = a[1]
b[2] = a[2]
if b[1] > b[2] then t=b[1]; b[1]=b[2];  b[2]=t
b[3] = a[3]
if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
for (i = 4; i <= n; i = i+1)
  if a[i] < b[3] then b[3] = a[i]
  if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
  if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
return b[3]

Answer 1

It is linear, as the only inner loop repeats at most n times, and performs only constant time operations.

More specifically

1. b[1] = a[1]
2. b[2] = a[2]
3. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
4. b[3] = a[3]
5. if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
6. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
7. for (i = 4; i <= n; i = i+1)
8. | if a[i] < b[3] then
9. | | b[3] = a[i]
10. | | if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
11. | | if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
12. return b[3]

Lines 1-6 are executed only once and should be constant time. In the context of a single run through the for loop, Lines 8-11 are executed only once, and are all constant time operations; which are then repeated ~n-3 times.

Answer 2

A good rule of thumb is: how many times do you loop over the input?

Answer 3

This is O(n), it is always good to look at what the input is, and see what changes if you were to add another element to the array in this case.

You will find that you will have to scan over the array to find the 3rd smallest element in the array.