Mazdak Farrokhzad edited Version1.tex  over 10 years ago

Commit id: 92f6502fd6ba8be3e3cbe6d763e3b63dc47c7884

deletions | additions      

       

Estimating constants:  \begin{enumerate}  \item method scope, outside all loops:  \\$a = assignment, outerLoopInit, initMaxSum + outerLoopInit + outerLoopCondExtra +  return = 1 + 1 + 2 +  1 = 3$ 5$  \item outer loop:  \\$b = forLoopTurn + middleLoopInit + middleLoopCondExtra  = 2 3  + 1 + 2  = 3$ 5$  \item middle loop:  \\$c = forLoopTurn + thisSum initThisSum  + innerLoopInit + innerLoopCondExtra +  branch = 2 3  + 1 + 1 2  + 4 8  = 8$ 14$  \item inner loop:  \\$d = forLoopTurn + addThisSum = 2 3  + 1 = 3$ 4$  \end{enumerate}  Finally, substitute constants:  $$  T(n) = \frac{1}{2}(n^3 \frac{2}{3}n^3  + 11n^2 9n^2  + 16n \frac{40}{3}n  + 6) 5)  \in \mathcal{O}(n^3) $$