Loop Analysis
CSE2321: Foundations 1

Now we’re at the meat of this class. Everything that we’ve been doing until now has been building up to this.

Estimating Execution Time

To estimate the amount of time that a given algorithm runs we assign some constant amount of time to each statement.

Basics of Time Estimation

Let’s say we wanted to estimate the time of the following algorithm:

\begin{algorithm} \State $x = 0$ \For{$i = 1$ to $25$} \State $x = x + 1$ \EndFor \end{algorithm}

We could do this by assigning a constant time to each line. But we have to be careful about the for loop since it runs multiple times. After we assign times it should look like this:

\begin{algorithmic} \State $x = 0$ \Comment $c_1$ \For{$i = 1$ to $25$} \State $x = x + 1$ \Comment $25 c_2$ \EndFor \end{algorithmic}

Double For Loops

x = 0
for i = 1 to n do
    for j = i to n do
        x = x + i - j
    endfor
endfor

Translating the code into a summation is our main job here.

\begin{align*} T(n) &= \sum_{i = 1}^{n} \sum_{j = 1}^{i} c \\ T(n) &= \sum_{i = 1}^{n} c \cdot i \\ T(n) &= c \sum_{i = 1}^{n} i \\ T(n) &= c \cdot \frac{n (n + 1)}{2} \\ T(n) &\in \Omega(n^2) \end{align*}

Worked Triple Summation Example

While Loops

While Loops are very similar to For Loops but they do have some differences.

It is hard to tell how many times a While Loop runs just by looking at it.

Determining the Number of Iterations

Because this is hard to do with While Loops, we want to draw a table comparing the number of iterations and the value of the variable we’re iterating over. This will help us find a pattern.

Example

while i <= n i = i + 10

# of iterations	value of i
0	0
1	10
2	20
3	30
4	40
…	…
k	10k

1E From Homework

First analyze the iteration of the while loop
Now we have a for loop in sigma notation that we need to bound.
We should find this to be $T(n) \in \Theta(n^3)$

Loop Analysis CSE2321: Foundations 1