Intro to Algorithms: Peak Finding Algorithm 1

When we design an algorithm we are majorly concerned with two things:

1. Accuracy or correctness of the algorithm
2. Time complexity of the algorithm (in other words the worst case scenario in terms of time taken)

Let me first define what is a peak, then we will try an find ways to "Find a peak if it exists"

Peak in 1D array

Consider a 1D array of n elements: A = [ a₁, a₂, ...., a_n ], then i^th element a_i is a peak iff :

a_i-1 le a_i AND a_i+1 le a_i

A straightforward algorithm to do this would be:

1. Start from array index = 0
2. Compare the element with its right element, if it is greater than or equal to the right element. It is the peak.
3. Else increase index repeat the steps 2 and 3 till peak is found or all elements of the array are traversed.
4. The last element is the peak.

Python Code

  import numpy as np 
  n = 20  # Number of elements in the array
  # Generate a random array of 20 integers within range [0, 100]
  a = np.random.randint(100, size = n)  
  for i in range(n-1):
      if a[i] >= a[i+1]:
             print("Peak is {} at position {}".format (a[i], i))
             break
      elif i == n-2:
             print("Peak is {} at position {}".format (a[i+1], i+1))

Time Complexity

In the above algorithm we can see that in worst case scenario (when the peak is the last element of the array) we need to make n comparisions, thus the time complexity in Big O notation is O(n)

Abbrevations:

• iff if and only if
• le less than or equal to

To be Contd...

For any programming job, knowledge of algorithms is a must. Thus, comes this post, a follow-up to the MIT 6.006 Introduction to Algorithms course. I will continue writing about different algorithms taught in the course and their analysis. I hope they help someone getting a better understanding and finally a job.

Your upvotes, and comments will help me stay motivated. Follow me to stay updated
Cheers
Seben OfNine