1 votes 1 votes What is the space complexity of fractional knapsack algorithm? Alakhator asked Oct 9, 2018 Alakhator 1.4k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Somoshree Datta 5 commented Oct 21, 2018 reply Follow Share @Magma why is it O(n)? We dont require any extra space .The weights of the items and their corresponding profits are given as inputs to the algorithm. They wont be counted as extra space. Answer should be O(1). 0 votes 0 votes Magma commented Oct 21, 2018 reply Follow Share we need an extra space (array) to store (profit/weight) ratio 1 votes 1 votes Somoshree Datta 5 commented Oct 21, 2018 reply Follow Share oh yes..You r right 0 votes 0 votes Please log in or register to add a comment.