Input: Set of machines M, Each machine has an availability array D_m[t], 
set of activities A, for each activity j its starting time s_j,
its duration p_j and its consumption in D during processing. 

Output: True or False if the usage for  each machine at each instant is less than the availability 

for each machine m in M

  usage := array[0..L] of zeros
  for each activity j in A
    usage[s_j] += c_{j,k}
    usage[s_j + p_j] -= c_{j,k} 
  for each time t in [1, L]
    if usage == 0
       usage[t] += usage[t-1]
  for each time t in [0, L-1]
    if usage[t] > D_m[t]
      return false

return true

The complexity is $O(|M| * (L + |A|))$. But $L$ is not an input length, it's a numerical value. I guess it's pseudo-polynnomial (Am I right ?)

How to prove that there is no better alternative, In other words that its also $\Omega(|M| * (L + |A|))$


1 Answer 1


I presume that $L$ is the length of $D_m$ for all machines. Hence your input is of size $O(|M|\cdot (L+|A|))$ because it contains $|A|$ activities for all machines and the $D_m$ array of length $L$ for all machines. Your runtime is $O(|M|\cdot (L+|A|))$. Thus your algorithm runs in linear time with respect to your input (meaning your algo is not pseudo-polynomial it is in fact polynonmial and even linear).

If a value in $D_m$ could be below $0$ we would have to check every value in $D_m$ for every machine at least once and for every activity that $D_m$ is large enough making the minimum runtime $\Omega (|M|L + |M||A|) = \Omega (|M|(L+|A|))$ and thus your algo optimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.