CODEWITHSUNDEEP
algorithmbig-o
Bilson
Bilson

Reputation: 1

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:

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]

Upvotes: 0

Views: 782

Answers (4)

Loqa
Loqa

Reputation: 79

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)

Upvotes: 0

CoderTao
CoderTao

Reputation: 4001

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.

Upvotes: 2

mduvall
mduvall

Reputation: 1038

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.

Upvotes: 0

dameiss
dameiss

Reputation: 91

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

Upvotes: 5

Related Questions