# How to prove that there is no better algorithm

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|))$$

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.