## 5 An O(1)-Competitive Algorithm
### Potential Function \(\Phi(t)\)
**_If \(n_{a}>m\) and \(imp_{lg_{u}}>\eta^{\alpha}\)_  
(a) \(\frac{d\Phi_{uu}}{dt}\leq\left(\frac{1}{1-\delta}\right)\cdot imp_{lg_{u}}\); (b) \(\frac{d\Phi_{uu}}{dt}\leq-\frac{\left(1+\
icefrac{{\Delta}}{{3m}}\right)}{ \left(2-2\delta\right)}\left(\frac{imp_{lg_{u}}^{2}}{imp_{uu}}\right)\)__  
**Proof. ** If \(n_{a}>m\) then:(a) It is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor u. To calculate the upper-bound, the worst-case is considered which occurs if Opt executes a job on u with the largest coefficient \(c_{\lg_{u}}~{}=~{}\left(\frac{1}{1-\delta}\right)\)-\(\textit{imp}_{\lg_{u}}\cdot\eta^{-1}\) (as \(\textit{imp}_{uu}\geq~{}\textit{imp}_{\lg_{u}}\succ\eta^{\alpha}\)). At this time, \(\omega_{i}\) increases at the rate of \(s_{uo}\) (because of Opt on \(u\)). \[ \begin{array}{ll}\frac{d\Phi_{uu}}{dt}&\leq c_{\lg_{u}}\cdot s_{uo}\\ &=\left(\frac{1}{1-\delta}\right)\textit{imp}_{\lg_{u}}\cdot\eta^{-1}\cdot s_{uo }\\ &\leq\left(\frac{1}{1-\delta}\right)\textit{imp}_{\lg_{u}}\cdot\eta^{-1}\cdot \eta~{}\left[\cdot\cdot\cdot s_{uo}\leq\eta\right]\\ \\ &\frac{d\Phi_{uo}}{dt}\leq\left(\frac{1}{1-\delta}\right)\textit{imp}_{\lg_{u}} \end{array}  \tag{15}\]  
(b) Next, it is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\). To compute the upper-bound, consider that a lagging job \(j_{i}\) on \(u\) is executed at the rate of \(\left(s_{uu}\cdot\frac{\textit{imp}_{u}(j_{i})}{\sum_{i=1}^{n_{u}}\cdot\textit {imp}_{u}(k)}\right)\) or \(\left(s_{uu}\cdot\frac{\textit{imp}_{u}(j_{i})}{\textit{imp}_{u}}\right)\), therefore the change in \(\omega_{i}\) is at the rate of \(\left(-s_{uu}\cdot\frac{\textit{imp}_{u}(j_{i})}{\textit{imp}_{u}}\right)\). To make the discussion uncomplicated, let \(h_{ui}~{}=~{}\sum_{k=~{}1}^{i}\textit{imp}_{u}(j_{k})\), \(h_{u0}=0,h_{ulg_{u}}=\textit{imp}_{lg_{u}}\succ\eta^{\alpha}\), \(\textit{imp}_{uu}\geq~{}\textit{imp}_{\lg_{u}}\succ\eta^{\alpha}\) and \(\textit{imp}_{u}(j_{i})~{}=~{}h_{ui}-h_{ui-1}\). Let \(z<l_{u}\) be the largest integer such that \(h_{uz}\leq\eta^{\alpha}\). (using Equation (3)):  
\[ \begin{array}{ll}\frac{d\Phi_{uu}}{dt}&=\sum_{i=~{}1}^{lg_{u}}c_{i}\cdot \left(-s_{uu}\cdot\frac{\textit{imp}_{u}(j_{i})}{\textit{imp}_{u}}\right)\\ &=-\left(\frac{s_{uu}}{\textit{imp}_{uu}}\right)\left(\sum_{i=~{}1}^{z}\left( \textit{imp}_{u}(j_{i})\cdot(h_{ui})^{1-2\delta}\right)+\sum_{i=~{}z+1}^{lg_{ u}}\left(\left(\frac{1}{1-\delta}\right)\left(\textit{imp}_{u}(j_{i})\cdot h_{ui} \cdot\eta^{-1}\right)\right)\right)\\ &\leq-\left(\frac{s_{uu}}{\textit{imp}_{uu}}\right)\left(\left(\left(\frac{ l_{u_{u}}}{2-2\delta}\right)+\left(\left(\frac{1}{1-\delta}\right)\cdot\eta^{-1} \cdot\left(\int_{h_{u_{u_{u_{u}}}}}^{h_{ulg_{u}}}fdf\right)\right)\right) \right.\\ &=-\left(\frac{s_{uu}}{\textit{imp}_{u}}\right)\left(\frac{h_{u_{u}}}{2-2 \delta}\right)+\frac{h_{ulg_{u}}-h_{u_{u_{u}}}}{(2-2\delta)\cdot\eta}\right) \\ &=-\left(\frac{s_{uu}}{\textit{imp}_{u}}\right)\left(\frac{h_{u_{u}}}{(2-2 \delta)h_{u}^{\gamma_{1}}}+\frac{h_{ulg_{u}}-h_{u_{u_{u}}}}{(2-2\delta)\cdot \eta}\right)\\ &\leq-\left(\frac{(1+\
icefrac{{\Delta}}{{3m}})\cdot\eta}{\textit{imp}_{uu}} \right)\left(\frac{h_{u_{u}}}{2-2\delta}\right)+\frac{h_{ulg_{u}}-h_{u_{u_{u}}} }{(2-2\delta)\cdot\eta}\right)\left\{\because\,h_{u_{u}}\leq\eta^{\alpha}~{} \right\}\\ &=-\frac{(1+\
icefrac{{\Delta}}{{3m}})\cdot\eta}{\textit{imp}_{uu}}\cdot \frac{h_{ulg_{u}}}{(2-2\delta)}\\ &=-\frac{(1+\
icefrac{{\Delta}}{{3m}})\cdot\eta}{(2-2\delta)}\cdot\left(\frac{ \textit{imp}_{\lg_{u}}}{\textit{imp}_{uu}}\right)\\ \end{array}  \tag{16}\]  
\(\Box\)  
**Lemma 6**: _At all time \(t\), when \(\Phi\) does not comprise discrete alteration \(\frac{d\Theta_{uu}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\leq c\cdot\frac{d\Theta _{uu}}{dt}\), where \(c~{}=~{}\left(\frac{9}{8}+\frac{3\Delta}{8}\right)\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}\right)\). Assume that \(\gamma~{}=~{}\frac{1}{16}\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{ \alpha}\right)\)._  
**Proof.