I need to calculate the time complexity of the following code:
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
Is it O(n^2)?
Yes, nested loops are one way to quickly get a big O notation.
Typically (but not always) one loop nested in another will cause O(n²).
Think about it, the inner loop is executed i times, for each value of i. The outer loop is executed n times.
thus you see a pattern of execution like this: 1 + 2 + 3 + 4 + ... + n times
Therefore, we can bound the number of code executions by saying it obviously executes more than n times (lower bound), but in terms of n how many times are we executing the code?
Well, mathematically we can say that it will execute no more than n² times, giving us a worst case scenario and therefore our Big-Oh bound of O(n²). (For more information on how we can mathematically say this look at the Power Series)
Big-Oh doesn't always measure exactly how much work is being done, but usually gives a reliable approximation of worst case scenario.
4 yrs later Edit: Because this post seems to get a fair amount of traffic. I want to more fully explain how we bound the execution to O(n²) using the power series
From the website: 1+2+3+4...+n = (n² + n)/2 = n²/2 + n/2. How, then are we turning this into O(n²)? What we're (basically) saying is that n² >= n²/2 + n/2. Is this true? Let's do some simple algebra.
It should be clear that n² >= n (not strictly greater than, because of the case where n=0 or 1), assuming that n is always an integer.
Actual Big O complexity is slightly different than what I just said, but this is the gist of it. In actuality, Big O complexity asks if there is a constant we can apply to one function such that it's larger than the other, for sufficiently large input (See the wikipedia page)
May I ask a small question here? what if the "//some code" part is some computation with O(N) complexity, how is the result calculated? I think this is the common case where one function calls another and considers the later as a black-box having some complexity provided by specs?
@ShawnLe: Insightful observation. In most assumptions, yes, we assume that
//some code
is O(1), and therefore does not get factored into Big O complexity. If it were in fact O(N), then our overall complexity becomes O(N^3). Think of it as multiplication (because it is). For ~N outer loop iterations, the inner loop iterates ~N times, with each iteration performing ~N work. N times N times N = N^3.Dont forget heapifying a heap is two nested loops (as you build the heap), but its O(n).