Simple Algorithm time complexity Question

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
• Te开发者_Python百科mporary 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]

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

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.

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.

The time complexity is linear which is O(n). You are doing iterative only once starting from 4 to n. Thus time complexity is O(n)