sri ramanuja seva

Task – Find the smallest value in an array.

Now, if we are told that the array is already sorted (say, in ascending order), then our task is trivially done, The answer is direct. The 1st element in the array is the minimum value.

e.g. Let’s say the array is: 5 | 12 | 20 | 22 | 31 | 42

‘5’, the 1st element in the sorted array is the minimum element.

We are going to assume that the array is not sorted.

Lets say the array has n elements.

• In order to find the minimum value, we necessarily (compulsorily) need to look at all the n elements of the array.
• Why so?
  • Any element in the array could be the minimum. Hence, we cannot afford to ignore or skip any element, since that element may well be the minimum.

So, we have established that we need to look at each and every element of the array.
Let’s do one thing:
We’ll keep track of the smallest value we’ve encountered so far. That is, as the traverse the array element-by-element, we’ll make note of the smallest value we’ve encountered so far.
When we’ve traversed the entire array, that is, when we’ve looked at each and every element of the array, the smallest value encountered among these elements is simply the minimum value in the array

---

Example:

Array A, having n = 5 elements.
10 | 13 | 8 | 6 | 11
The array elements are indexed from 1 to 5. (That is, A[1] is 10; A[2] is 13, and so on,)

• We look at the 1st element – A[1], which is 10.
  • We’ve looked at only one element so far. So, the smallest value we’ve encountered so far is 10. We’ll store this in a variable called Min_So_Far (this variable keeps track of the smallest value encountered so far.)
    
• Next, we go to the next element – A[2], which is 13.
  • We compare this with Min_So_Far, which is 10,
  • The minimum value we’ve encountered so far is 10, and the current element (A[2]) is 13.
  • So, the minimum value we’ve encountered so far remains as 10, No change.
    
• Look at the next element (A[3]), which is 8.
  • Compare this with Min_So_Far, which is 10.
  • Current element (8) is less than Min_So_Far (10).
  • So, the minimum value we’ve encountered so far is actually 8. We need to update Min_So_Far. Set Min_So_Far to be 8,
    
• We go on to A[4], which is 6,
  • Min_So_Far is 8.
  • A[4] is less than Min_So_Far.
  • so, again, we need to update Min_So_Far. Set Min_So_Far to be 6. (That is, 6 is the smallest value we’ve encountered so far.)
    
• We go on to A[5], wbich is 11.
  • Min_So_Far is 6.
  • Min_So_Far is less than A[5]. So, no need to change Min_So_Far. The smallest value we’ve encountered remains 6.
    
• We’ve reached the end of the array. No more elements to look at. We’ve looked at each and every element of the array, and Min_So_Far (that is, the smallest value encountered so far) is 6. That is, in other words, 6 is the smallest value in the entire array.
• Our task was to find the smallest value in the array. So, our task is successfully accomplished.

---

Let’s look at another example. (Depicted in the following image)

---

Pseudo-code

Here’s the pseudo-code for the algorithm:

---

Some comments on the above pseudo-code:

• Line 1: Initially, we’ve encountered only one element so far. Hence, Min_So_Far is set to A[1].
• Line 2: We run a loop from the 2nd element to the last element.
• Lines 3 to 5: Each time we encounter an element, we compare it with Min_So_Far, and if it is less than Min_So_Far, we update Min_So,Far.
• Line 6: We are now out of the loop. The value in Min_So_Far is the smallest value in the array. Display it.

---

Time Complexity/Running time analysis

• Line 1 takes constant, that is, O(1), time. (We just make an assigment.)
• SImilarly, Line 6 (displaying the min value) takes O(1) time.
• In Lines 2 to 5, there is a for loop.
  • n-1 iterations. That is, O(n) iterations.
    • In each iteration, we make a comparison, which is an O(1) time operation.
    • In each iteration, optionally we make an assigment. That is also an O(1) time operation.
    • So, time required in a single iteration is O(1).
  • Therefore, time required for O(n) iterations is O(n). \
• Hence, combining the times mentioned above: O(1) + O(1) {for Lines 1 and 6} + O(n) {for the loop}, the time complexity of the algorithm is O(n).
• That is, it is a linear-time algorithm (The running time is a linear function of the input size in big-O notation.)

Similar posts on algorithms: How to insert element in an array? , Selection Sort Algorithm