Mazdak Farrokhzad edited Version2.tex  over 10 years ago

Commit id: e59961f6daa92ae474524eab84be566429c4e332

deletions | additions      

       

Estimating constants:  \begin{enumerate}  \item method scope, outside all loops: scope + ...:  $a = assignment, outerLoopInit, initSums + outerLoopInit + outerLoopCondExtra +  return = 1 + 1 + 2 +  1 = 3$ 5$  \item outer loop: $b = forLoopTurn + assignThisSum + innerLoopInit + innerLoopCondExtra  = 2 3  + 1 + 1 + 2  = 4$ 7$  \item inner loop: $c = forLoopTurn + addThisSum + branch = 2 3  + 1 2  + 4 8  = 7$ 13$  \end{enumerate}  Finally, substitute constants:  $$  T(n) = \frac{1}{2}(7n^2 \frac{1}{2}(13n^2  + 15n 27n  + 6) 10)  \in \mathcal{O}(n^2) $$