Question

You are given an array A consisting of strings. You have an algorithm MULTI_SORT that sorts each of the string and further, sorts the array A. What would be the runtime for the algorithm MULTI_SORT if,

There are N1 elements in A,

Each string in A has a length N2 ,

Each sorting algorithm has a big-O runtime: (number of elements to sort) X log (number of elements to sort).

Answer 1

Solution:

So, the MULTI_SORT algorithm is sorting the strings inside the array and then the array itself

we can see that the string lengths inside the array is N2, so it will take N2 log N2 time to sort the strings

there are N1 number of elements inside the array which means it will take N1 log N1 time to sort the array.

so the total complexity of the MULTI_SORT algorithm will be

T(n)= N1 * N2 log N2 + N1 log N1

T(n)= O(N1*(max(N2 log N2, log N1))

Explanation:

since we don't know the if N1>N2 or N2>N1, hence the max(N2 log N2, log N1), will decide the upper bound of the algorithm.

Hit the thumbs up if you liked the answer. :)

Hit the thumbs up if you liked the answer. :)