##      
### Overview

The **complexity** of an algorithm is defined as the interval of time an algorithm takes to process a provided input. An algorithm can process its provided input in constant, linear, quadratic, exponential, and logarithmic time. 

The term **Big O** refers to the complexity of an algorithm. An algorithm's complexity increases with the time it takes to run the algorithm. 

> We define complexity in terms of $O(1)$, $O(n)$, $O(n^2)$, $O(n^n)$, and $O(log n)$.
>- $O(1)$  refers to the program executed in constant time.
>- $O(n)$ refers to the program executed in linear time.
>- $O(n^2)$ refers to the program executed in quadratic time
>- $O(n^n)$ refers to the program executed in exponential time
>- $O(log n)$ refers to the program executed in logarithmic time

In this shot, we will sort an array of a's and b's in linear time. 

### Example

Let's consider a one-dimensional array of a's and b's, as shown below:



Now we have to sort the given array in ascending order in linear time O(n). After sorting, the array will look like the array given below.

### Code implementation

Let's solve this example using Python.

def sortanb(arr):
  countofa=0;
  for i in range(len(arr)):
    if arr[i]=='a':
      countofa+=1
  countofb=len(arr)-countofa
  for j in range(len(arr)):
    if j<=countofb:
      arr[j]='a'
    else:
      arr[j]='b'
  
if __name__ == "__main__":
  array="ababaab"
  arr = [char for char in array]
  sortanb(arr)
  print("Here is the sorted array :")
  print(arr)

### Code explanation
- Lines 3–5: We count the number of a's in the input array.
- Line 6: We count the number of b's by subtracting the `countofa` from the `len(input_array)`, which is the length of the input array.
- Lines 7–11: We fill the array with the respective number of a's and b's.
- Line 14: We define a string of a's and b's.
- Line 15: We convert the string into a char array.
- Line 16: We call the function `sortanb(input_array)` to sort the char array.
- Lines 17–18: We print the sorted array.




How to sort an array of a's and b's in O(n)

Overview

Example

Code implementation

Code explanation