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.
That's really clever. I wonder how the time complexities stack up for adding everything to the arrays and then sorting them vs just adding everything and iterating over them.
I'm trying to learn how to analyze time complexities so here's my stab at it:
Creating the array would be O(n) and then running through it would be O(n) as well so O(2n) total which reduces to O(n)
Using radix sort you'd have O(n) for creating the array + O(nk) for radix sort it'd be O(2nk) or O(nk)
So that would mean that simply iterating would be slightly faster?
Am I right about that or do is my understanding of time complexities still off kilter?
Side note: hackerrank needs comment formatting.
Edited to fix time complexity for radix sort to O(nk) not O(n+k). I can't read charts.
Angry Professor
You are viewing a single comment's thread. Return to all comments →
That's really clever. I wonder how the time complexities stack up for adding everything to the arrays and then sorting them vs just adding everything and iterating over them. I'm trying to learn how to analyze time complexities so here's my stab at it:
Creating the array would be O(n) and then running through it would be O(n) as well so O(2n) total which reduces to O(n)
Using radix sort you'd have O(n) for creating the array + O(nk) for radix sort it'd be O(2nk) or O(nk)
So that would mean that simply iterating would be slightly faster?
Am I right about that or do is my understanding of time complexities still off kilter?
Side note: hackerrank needs comment formatting.
Edited to fix time complexity for radix sort to O(nk) not O(n+k). I can't read charts.