Trusted answers to developer questions

Educative Team

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.

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

Input: An array of a's and b's

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.

Output: The array of a's and b's sorted

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)

Sorting an array of a's and b's in linear time

- 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.

RELATED TAGS

algorithm

python

time

complexity

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses