Time complexity for Sample Online Data 5.13

#1

The book says time complexity for the brute-force solution is o(nk). Isn’t this wrong? We are first reading all elements which will take O(n) time and O(n) memory. Then we are essentially using the same solution for 5.12 (Sample Offline Data) to get the random subset. This will take O(k) additional time. So the total time complexity should be O(n+k). Now since k<n and k=n in worst case, time complexity drops to O(2n) or O(n). Whereas according to the book, the worst case complexity seems to be O(n*n) or O(n^2). And this is not true. How can I get this rectified for future versions?

0 Likes