Question

What is the Big O of the following algorithms along with the worst and average cases:

Euclid's Algorithm

Brute-Force Matching

Topological Sort

Lomuto Partition

Russian Peasant Algorithm

Answer 1

1) In euclid's algorithm we take bigeer number modulo small number in each iteration. So the complexity in average case as well as worst case is log(min(m,n)), where m and n are the numbers we want to find gcd of.

2) Brute force matching is basically an algorithm for matching two string patterns. As we're using the brute force approach we'll start with each index of a string and match the characters with each character of the second string. Here the complexity in average case as well as worst case is m*n, where m and n are the lengths of the strings.

3) Topological sorting is basically the same as DFS just with an extra stack. So the complexity in average case as well as worst case will be V+E.

4) Lumuto partition is the same method as we use in quick sort we take a pivot in the array and and swap the elements to make the left elements smaller and right elements bigger. So the complexity in average case is n/2 and in the worst case is n.

5) Russian peasent algorithm we right shift the smaller number untill it becomes 0 so the complexity in average case as well as worst case will be log(min(m,n)), where m and n are the numbers we want to find product of.