algorithmic complexity in Big O notation

Question

Here is the function that is meant to be analyzed

f1(n)
1 v ← 0
2 for i ← 1 to n
  3 do for j ← n + 1 to 2n
   4 do v ← v + 1
5 return v

I was wondering if my rationalization is correct for big O().

I rewrote the values as summations, I got n^2 + n as the final result for the sum in terms of n. This means the big O notation would be n^2. But when I rationalize it I fihured it would be lower. Any help?

Answer 1

The outer loop is $O(n)$ and the inner loop is $O(n)$. So we multiply to get $O(n^{2})$. Your analysis is correct.

Edit: A runtime analysis of your program.

Consider:

$$T(n) = 2 + \sum_{i=1}^{n} \sum_{j=n+1}^{2n} 1 = 2 + \sum_{i=1}^{n} \sum_{j=1}^{n} 1 = 2 + \sum_{i=1}^{n} n = n^{2} + 2 = O(n^{2})$$

So the $2$ term in $T(n)$ accounts for lines (1) and (5). The first summation is your outer loop, and the inner summation is your inner loop. Line (4) does not rely on the index $j$ at line (3), so I just shifted the $j$ index and range down by $n$.

This is a good tutorial on complexity analysis if you are interested in more reading. Let me know if I can clarify further: http://www.dreamincode.net/forums/topic/321402-introduction-to-computational-complexity/