in reply to Re: Re: finding top 10 largest files
in thread finding top 10 largest files

Yes, you could. I realized that, but didn't present it, because it's neither efficient memory wise (as you are processing all the file names at the same time), nor is it run-time efficient, as you are sorting all the file names, and that's Omega (N log N). The solution where you keep a sorted buffer takes linear time.

If you want to factor in the amount of files (let's say k) to be reported, the solution you present takes O (N log N + k), while my solution takes O (k N). If you replace the array with a heap, you can reduce that to O (k + N log k). The used memory in your solution is O (N), and O (k) in my solution.

All mentioned upperbounds are tight.

Abigail