All Courses
Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity Get the App Login Join for Free
Sign in Open App
GATE Exam  >  GATE Questions  >   You are given an array of strings, where dif... Start Learning for Free
SaveJoin the Discussion on the App
You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?
  • a)
    O(n)
  • b)
    O(n2)
  • c)
    O(logn)
  • d)
    O(loglogn)
Correct answer is option 'A'. Can you explain this answer?
FREE This question is part of
Download PDF Attempt Test
Download PDF Attempt this Test
Verified Answer
You are given an array of strings, where different strings may have d...
For the strings, we can do this
1. Groups the strings by length and order the groups
2. Starting i on the maximum length and going down to 1, perform counting sort on the ith character. Make sure to include only groups that have an ith character. If the groups are subsequent sub-arrays in the original array, we’re performing counting sort on a subarray ending on the last index of the original array.
So we ultimately using count sort, hence time complexity = O(n)
View all questions of this test
Most Upvoted Answer
You are given an array of strings, where different strings may have d...
Worst case time complexity of the best algorithm to sort the array


In order to determine the worst case time complexity of the best algorithm to sort the given array of strings, we need to analyze the characteristics of the array and the sorting algorithms.


Characteristics of the array


  • The array contains strings with different numbers of characters.

  • The total number of characters over all the strings is n.



Sorting algorithms

There are various sorting algorithms available, but the most commonly used ones are:


  • Quicksort

  • Mergesort

  • Heapsort

  • Insertion sort

  • Selection sort



Analysis

We can analyze the time complexity of each sorting algorithm in the worst case scenario:


  • Quicksort: The worst case time complexity of Quicksort is O(n^2), which occurs when the pivot chosen is either the smallest or largest element in the array, resulting in unbalanced partitions.

  • Mergesort: The worst case time complexity of Mergesort is O(nlogn), as it consistently divides the array into halves until individual elements are reached, and then merges them back in sorted order.

  • Heapsort: The worst case time complexity of Heapsort is O(nlogn), as it builds a heap data structure and repeatedly extracts the maximum element from it.

  • Insertion sort: The worst case time complexity of Insertion sort is O(n^2), as it iterates over the array and repeatedly inserts each element into its correct position in the sorted portion of the array.

  • Selection sort: The worst case time complexity of Selection sort is O(n^2), as it repeatedly selects the minimum element from the unsorted portion of the array and places it in its correct position.



Conclusion

Among the given sorting algorithms, the best algorithm in terms of worst case time complexity is Insertion sort with a time complexity of O(n^2). However, it is important to note that this time complexity is not optimal for large values of n. Other algorithms like Mergesort and Heapsort, with a time complexity of O(nlogn), are more efficient in practice.


Answer

The worst case time complexity of the best algorithm to sort the given array of strings is option 'A' - O(n).
< Previous Question Next Question >
Explore Courses for GATE exam

Similar GATE Doubts

The procedure given below is required to find and replace certain characters inside an inputcharacter string supplied in array A. The characters to be replaced are supplied in array oldc,while their respective replacement characters are supplied in array newc. Array A has a fixedlength of five characters, while arrays oldc and newc contain three characters each. However, theprocedure is flawedvoid find _ and _ replace (char *A, char *oldc, char * newc ) {for (int i= 0; i <5; i++)for (int j =0; j <3; j++)if (A [i] ==oldc[ j]) A [i]= newc [j] ;}The procedure is tested with the following four test cases(1) oldc = "abc", newc = "dab" (2) oldc = "cde", newc = "bcd"(3) oldc = "bca", newc = "cda" (4) oldc = "abc", newc = "bac"Q.The tester now tests the program on all input strings of length five consisting of characters‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with thefour test cases given above, how many test cases will be able to capture the flaw?

You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer?
Question Description
You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer?.
Solutions for You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE. Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer?, a detailed solution for You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? has been provided alongside types of You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. What is the worst case time complexity of the best algorithm to sort this array?a)O(n)b)O(n2)c)O(logn)d)O(loglogn)Correct answer is option 'A'. Can you explain this answer? tests, examples and also practice GATE tests.
Explore Courses for GATE exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Get App
© EduRev
Education Revolution
Follow Us
Signup to see your scores go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup