## 5 An O(1)-Competitive Algorithm
### Potential Function \(\Phi(t)\)
(using Equations (8) and (9))  
\[\frac{d\Phi_{u}}{dt}\leq\left(\frac{s_{ua}}{\alpha}+\left(1-2\delta\right) \cdot imp_{lg_{u}}\right)-\left(s_{ua}\cdot imp_{lg_{u}}\
icefrac{{1-2\delta} }{{2}}\right) \tag{21}\]  
(by using Equations (1) and (21))  
\(\frac{dG_{uu}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\)  
\(\leq\left(imp_{ua}+s_{ua}^{\alpha}+\gamma\cdot\left(\left(\frac{s_{ua}}{\alpha }+\left(1-2\delta\right)\cdot imp_{lg_{u}}\right)-\left(s_{ua}\cdot imp_{lg_{u }}\
icefrac{{1-2\delta}}{{2}}\right)\right)\right)\)  
\(=\left(imp_{ua}+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{\alpha}\cdot imp_{ uu}+\frac{\gamma}{\alpha}s_{ua}^{\alpha}+\gamma\cdot\left(1-2\delta\right) \cdot imp_{lg_{u}}-\gamma\cdot\left(1+\
icefrac{{\Delta}}{{3m}}\right)\cdot imp _{ua}\
icefrac{{1/\alpha}}{{3m}}\cdot imp_{lg_{u}}\
icefrac{{1-2\delta}}{{2}}\right)\)  
\(\leq\left(\frac{\gamma}{\alpha}s_{ua}^{\alpha}+\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}\right)\cdot imp_{ua}+\gamma\cdot\left(1-2 \delta\right)\cdot imp_{ua}-\gamma\cdot\left(1+\
icefrac{{\Delta}}{{3m}} \right)\cdot imp_{ua}\
icefrac{{1/\alpha}}{{3m}}\left(\left(1-\left(\frac{3} {3+\Delta}\right)\right)\cdot imp_{ua}\right)\
icefrac{{1-2\delta}}{{2}}\right)\)  
\(=\left(\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{ua}\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}+\gamma\cdot\left(1-2\delta\right)-\gamma \cdot\left(1+\
icefrac{{\Delta}}{{3m}}\right)\cdot\left(\frac{\Delta}{{3+ \Delta}}\right)^{1-2\delta}\right)\right)\)  
\(\leq\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{ua}\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}+\gamma-\gamma\cdot\left(\frac{\Delta}{{3+ \Delta}}\right)\right)\)  
\(=\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{ua}\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}+\gamma\cdot\left(\frac{\Delta}{{3+\Delta}} \right)\right)\)  
\(\leq\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{ua}\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}+\gamma\right)\)  
\(=\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{ua}\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}+\frac{1}{16}\left(1+\left(1+\
icefrac{{\Delta }}{{3m}}\right)^{\alpha}\right)\right)\)  
\(\leq\frac{\gamma}{\alpha}s_{ua}^{\alpha}+\frac{imp_{ua}}{\mu}\left(\frac{17} {16}\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{\alpha}\right)\right)\)  
\(=\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{uo}\left(\frac{17}{16}\left(1+ \frac{\Delta}{{3}}\right)\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{ \alpha}\right)\right)\)  
\(\leq\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{uo}\left(\frac{9}{8}+\frac{3 \Delta}{8}\right)\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{\alpha}\right)\)  
\(\leq\frac{\gamma}{\alpha}s_{ua}^{\alpha}+imp_{uo}\left(\left(\frac{9}{8}+ \frac{3\Delta}{8}\right)\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{ \alpha}\right)\right)\)  
\(\frac{dG_{ua}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\leq\frac{\gamma}{\alpha} \cdot s_{ua}^{\alpha}+imp_{uo}\ c\)  
(22)  
Since \(c\ =\ \left(\frac{9}{8}+\frac{3\Delta}{8}\right)\left(1+\left(1+\
icefrac{{ \Delta}}{{3m}}\right)^{\alpha}\right)\) and \(\gamma\ =\ \frac{1}{16}\left(1+\left(1+\
icefrac{{\Delta}}{{3m}}\right)^{\alpha}\right)\), we have  
\(\Rightarrow c\ =\ \left(\frac{9}{8}+\frac{3\Delta}{8}\right)\cdot 16\gamma\Rightarrow\frac{ \gamma}{c}\ =\ \frac{1}{18+6\Delta}<1\Rightarrow\frac{\gamma}{c}<1\Rightarrow\gamma<c\)  
\(\(by using Equation (8))  
\[\frac{d\Phi_{u}}{dt}\leq\left(\frac{{s_{u}}^{\alpha}}{\alpha}+(1-2\delta)\cdot imp _{lg_{u}}\right) \tag{24}\]  
(by using Equations (1) and (24))  
\(\frac{dG_{uu}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\leq imp_{uu}+{s_{ua}}^{ \alpha}+\gamma\cdot\left(\frac{{s_{ua}}^{\alpha}}{\alpha}+(1-2\delta)\cdot imp _{lg_{u}}\right)\)  
\(=imp_{ua}+(1+\
icefrac{{\Delta}}{{3m}})^{\alpha}\cdot imp_{uu}+\frac{\
u}{ \lambda}\cdot{s_{u}}^{\alpha}+\gamma\cdot(1-2\delta)\cdot imp_{lg_{u}}\)  
\(\leq\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+imp_{uu}+(1+\
icefrac{{\Delta}}{{3m }})^{\alpha}\cdot imp_{uu}+\gamma\cdot(1-2\delta)\cdot imp_{uu}\)  
\(=\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+imp_{uu}\left(1+(1+\
icefrac{{\Delta} }{{3m}})^{\alpha}+\gamma\cdot(1-2\delta)\right)\)  
\(\leq\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+\frac{imp_{uu}}{\mu}\left(1+(1+ \
icefrac{{\Delta}}{{3m}})^{\alpha}+\gamma\cdot(1-2\delta)\right)\) (by using Equation (17))  
\(\leq\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+\left(\frac{1}{\mu}\left(\left(1+( 1+\
icefrac{{\Delta}}{{3m}})^{\alpha}\right)+\gamma\right)\right)\)\(imp_{uo}\)  
\(=\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+\left(\frac{1}{\mu}\left(\left(1+(1+ \
icefrac{{\Delta}}{{3m}})^{\alpha}\right)+\frac{1}{16}\left(1+(1+\
icefrac{{ \Delta}}{{3m}})^{\alpha}\right)\right)\right)\)\(imp_{uo}\) (by using Equation (19))  
\(=\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+\left(\frac{1}{16}\left(1+\frac{ \Delta}{3}\right)\left(1+(1+\
icefrac{{\Delta}}{{3m}})^{\alpha}\right)\right) \cdot imp_{uo}\) (by using Equation (18))  
\(\leq\frac{\
u}{\alpha}\cdot{s_{u}}^{\alpha}+(\left(\frac{9}{8}+\frac{3\Delta }{8}\right)\left(1+(1+\
icefrac{{\Delta}}{{3m}})^{\alpha}\right))\cdot imp_{uo}\)  
\(\leq c_{su}^{\alpha}+c\cdot imp_{uo}\) (by using Equations (18) and (23))  
\(\frac{dG_{uu}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\leq c\cdot({s_{u}}^{ \alpha}+{s_{u}}^{\alpha})\)  
\(\frac{dG_{uu}}{dt}+\gamma\cdot\frac{d\Phi_{u}}{dt}\leq c\cdot\frac{dG_{uo}}{dt}\)  
Hence the running condition is satisfied for \(n_{a}\leq m\), \(imp_{uu}\leq\eta^{\alpha}\), \(imp_{lg_{u}}\leq\eta^{\alpha}\), \(imp_{lg_{u}}\leq\left(imp_{ua}-\left(\frac{3}{3+\Delta}\right)imp_{ua}\right)\), \(c=\left(\frac{9}{8}+\frac{3\Delta}{8}\right)\left(1+(1+\
icefrac{{\Delta}}{{3m }})^{\alpha}\right)\).