Time Complexity analysis | 451. Sort Characters By Frequency

Leetcode Problem : https://leetcode.com/problems/sort-characters-by-frequency/

I had a doubt, can anyone help me here with it.
Three approach which we can use here, have all same time complexity right??

1st Approach - counting frequency of letters and sorting them

  • counting done in O(n) time and O(n) space
  • sorting done in O(nlogn) , where n = 26

2nd Approach - counting frequency of letters and using heap

  • counting done in O(n) time and O(n) space
  • Heapify list - O(n) time
  • Extracting letters - O(nlogn) time , where n=26

3rd Approach - Using bucket sort

  • counting done in O(n) time and O(n) space
  • Bucket sort - O(n) time

Note, for 1st and 2nd approach, O(nlogn) = O(n) , because log(26) = 4
So, is it correct to say that time complexity of all above approach are same or am i missing something here ????

Comments (0)