radix sort do following for each digit where varies from least significant digit to the most significant digit asort input array using counting sort (or any stable sortaccording to the 'th digit exampleoriginalunsorted list sorting by least significant digit ( placegives[*notice that we keep before because occurred before in the original listand similarly for pairs and sorting by next digit ( placegives[*notice that again comes before as comes before in the previous list sorting by most significant digit ( placegives what is the running time of radix sortlet there be digits in input integers radix sort takes ( *( + )time where is the base for representing numbersfor examplefor decimal systemb is what is the value of dif is the maximum possible valuethen would be (log ( )so overall time complexity is (( +blogb( )which looks more than the time complexity of comparison based sorting algorithms for large let us first limit let <nc where is constant in that casethe complexity becomes (nlog ( )but it still doesn' beat comparison based sorting algorithms linear search linear search is to check each element one by one in sequence the following method linearsearch(searches target in an array and returns the index of the targetif not foundit returns - which indicates an invalid index int linearsearch(int arr[]int target for (int arr lengthi++ if (arr[ =target return return -