Which algorithm has linear complexity O(n)?

An algorithm with linear complexity O(n) means that the execution time or the used memory grows proportionally to the size of the input data n. Examples of such algorithms include:

1. Finding the maximum or minimum element in an array: You need to go through all elements of the array once.

   # Finding the maximum element
   def find_max(arr):
       if not arr:
           return None
       max_val = arr[0]
       for element in arr:
           if element > max_val:
               max_val = element
       return max_val
   

2. Linear search: Searching for a specific element in an unordered list by sequentially checking each element.

   // Linear search
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element found
           }
       }
       return -1; // Element not found
   }
   

3. Counting the frequency of elements in a list: You need to go through the list once, using, for example, a hash table or dictionary.

   // Counting frequency of elements
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Simple copying of an array: Creating a new copy of an array by traversing all elements of the original array.

5. Calculating the sum of all elements in an array: Requires a single pass through all elements.

In all these examples, the number of operations is directly proportional to the number of elements in the data being processed.