The Branch and Bound algorithm's worst case runtime is bound by
, where n is the number of tasks. The worst case only
happens on an input instance where every node of the schedule tree
needs to be examined, or no groups of schedules can be skipped from
the upper and lower bound information. The number of partial schedule
nodes that would need to be examined in this case would be
which is in 
. The insert and delete
functions according to the LEDA manual take time in 
,
where k is the number of nodes in the heap. The size of the heap
will be about 
, which implies that insert and delete are 
in a measure of
the number of tasks. Every node that will be examined will need to be
at least deleted from the heap, with nodes taking time
to delete you get the run time bound by .