We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The program has two loops. The first loop has a constant number of iterations, i.e., 100 iterations. Therefore, the time complexity of the first loop is O(1).
The second loop has n iterations, where n is the size of the input array. Inside the loop, a constant amount of work is done in each iteration, i.e., incrementing the counter at an index in the frequency array. Therefore, the time complexity of the second loop is O(n).
Thus, the overall time complexity of the program is O(n).
Space Complexity:
The program creates a new array of size 100 to store the frequency counts. Therefore, the space complexity of the program is O(1) for the frequency array.
In addition, the program uses a few constant amount of space to store the input array and some loop variables. Therefore, the space complexity of the program is also O(1) for these variables.
Thus, the overall space complexity of the program is O(1).
functioncountingSort($arr){// Write your code here$res=[];for($i=0;$i<100;$i++){if(!isset($res[$i])){$res[$i]=0;}}for($i=0;$i<count($arr);$i++){$res[$arr[$i]]++;}return$res;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Counting Sort 1
You are viewing a single comment's thread. Return to all comments →
php :
Time Complexity:
The program has two loops. The first loop has a constant number of iterations, i.e., 100 iterations. Therefore, the time complexity of the first loop is O(1).
The second loop has n iterations, where n is the size of the input array. Inside the loop, a constant amount of work is done in each iteration, i.e., incrementing the counter at an index in the frequency array. Therefore, the time complexity of the second loop is O(n).
Thus, the overall time complexity of the program is O(n).
Space Complexity:
The program creates a new array of size 100 to store the frequency counts. Therefore, the space complexity of the program is O(1) for the frequency array.
In addition, the program uses a few constant amount of space to store the input array and some loop variables. Therefore, the space complexity of the program is also O(1) for these variables.
Thus, the overall space complexity of the program is O(1).