2

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up.

Sorry if this is a dumb question but say we have something like 

for i=4 to n^2
   for j = 5 to 3i log (i)
      s = s + ij

I would set this up with outer loop = sum from i=4 to n^2, inner loop sum from j = 5 to 3i log i, and finally a constant. I'm getting hung up on how to sum everything up. Can someone please explain this to me?

Antonio Vargas
  • 24,993
marj
  • 21
  • First consider the inner loop. How many iterations does this take, for fixed $i$? Then consider the outer loop, and take the sum of the number of iterations for each value of $i$. – TMM Mar 06 '14 at 14:14

2 Answers2

3

A simple way to determine runtime is to use summations. Each loop becomes a sum, where the lower index is the starting value of the loop and the upper index is the ending value of the loop. Because you're performing a constant time operation in the innermost loop, we are simply summing $1$: \begin{align}\sum_{i=4}^{n^2} \sum_{j=5}^{3i\lg i} 1 &= \sum_{i=4}^{n^2}3i\lg i - 5 + 1\\ &\approx\sum_{i=1}^{n^2}i\ln i\end{align} (I'm using $\approx$ to slide between expressions that are asymptotically equivalent throughout the problem.)

The last summation above is kind of difficult (its solution involves the hyperfactorial function). So, we switch to an approach that is accessible to more students: a summation may be approximated by an integral. So, we now compute: \begin{align} \sum_{i=1}^{n^2}i\ln i&\approx \int_1^{n^2}x\ln x\,dx \\ &\approx x^2\ln x + \mathcal O(x^2)\Bigg |_1^{n^2}\\ &\approx n^4\ln n \end{align}

So, your program executes with $\mathcal{O}(n^4\ln n)$ time complexity.

apnorton
  • 17,706
-1

Consider two loops $A$ and $B$ that are not nested. The body of A executes $n$ times and the body of B executes $k$ times. If we execute $B$ in the body of $A$, then $A$ still executes $n$ times, but $B$ executes whenever the body of $A$ executes. The body of $B$ executes $k$ times whenever the body of $A$ executes, and the body of $A$ executes $n$ times, so the body of $B$ executes $n \cdot k$ times.

When calculating the running time of an algorithm, you want to compare the number of steps in the algorithm to the input size. Say the input size for the algorithm $B$ nested inside of $A$ is $n$. You first want everything in terms of the input size, so say we know that $k = n/2$. Then the number of steps taken is $n \cdot k = 1/2 \cdot n^2 = c \cdot n^2 = O(n^2)$.

I hope this helps.

baffld
  • 165