I am working with the below algorithm, what would the worst case runtime for this be?

function BPP-O-Approximate(n,c,W)
     Initialize L as a list of n numbers.
     Initialize B as the list [c].
     k <- 1
     for i from 1 to n do
         x <- k + 1
         for j from 1 to k do
             if x = k + 1 and w_i ≤ b_k then
                 x <- k
             end if
         end for
         if x = k + 1 then 
             b_k+1 <- c; k <- k+1 
         end if
         l_i <- x; b_x <- b_x - w_i
      end for
      return L
  end function

I considered the case where all the objects have the same weight of c/2. In this case, each object can only fit in a bin on its own, so the algorithm will use n bins. Since there are n objects, the algorithm will perform n iterations of the loop, and in each iteration, it may need to search through all the bins to find one with enough space. In the worst case, each object will be placed in a new bin, and each bin will contain only one object, so the algorithm will perform n^2 operations.

To this logic, I think the worst case run time is O(n^2), does this look okay so far?


1 Answer 1


As an upper bound, suppose that k is incremented each iteration of the outter loop. On the first iteration of the main loop the inner loop executes once, on the second iteration the inner loop executes twice,…, on the xth iteration of the outter loop the inner loop executes x times.

The number of times the outter loop executes is n. The number of times the inner loop executes is O(1 + 2 + 3 + … n) = O(n(n + 1)/2) = O(n^2).

Mind O(n^2) is an upper bound on the total number of operations of the inner loop across all n iterations of the outter loop. All other operations in the outter loop may be assumed to take constant time O(1) per loop iteration - or a total of O(n) operations. Therefore the total execution time of the outter loop is O(n^2 + n) = O(n^2)

Outside of the outter loop - the largest operation is initializing the list of n terms, which should presumably take O(n) - unless you have some time consuming operation taking place there.

So yes, providing the list initialization doesn’t take any longer than O(n^2) then the total execution time of the algorithm has an upper bound of O(n^2).


You must log in to answer this question.