CODEWITHSUNDEEP
javaalgorithmfor-loopcomplexity-theorybig-o
rullzing
rullzing

Reputation: 642

Finding the computational complexity of a nested loop

I am having a hard time getting the complexity of this for-loop

for (i = 4; i < n; i++)
{
    for (j = i - 3, sum = a[i - 4]; j <= i; j++)
    {
        sum += a[j];
    }
    System.out.println("sum thru" + i + ": " + sum);
}

I was thinking that the complexity of this nested loop is n^2 since it's a nested loop but someone told me that this is incorrect and nested loops aren't always a quadratic complexity!

I don't really know how to get the complexity in a good way. I've seen lots of articles about Big-O and complexity but they weren't helpful because they were expecting me to know everything, and they examples weren't the same as any of the examples I have.

I am not asking for the answer, I'm asking for the method. Is there any formula or method that will work for everything in this topic? I want to know how to get the number of assignments but unfortunately I have no clue how to do this.

Can someone explain it to me step by step?

Upvotes: 3

Views: 1943

Answers (2)

Pan Long
Pan Long

Reputation: 1032

I don't think there is any formula that can solve all problems regarding to time complexity of algorithms. For me, the best way to figure out the big-O is going step by step, from the outer process to the inner process. I believe it is also the standard way for a beginner like you and me. For your question, first, the outer loop is O(n), which is straight forward. Then inside each loop, we have an inner process, which is another loop. That loop goes from i-3 to i, which is O(1). Then inside that process, it is a normal assignment statement, which is O(1) again. We take all together, the big-O will be O(n) * O(1) * O(1) = O(n)

Upvotes: 0

Ragavan
Ragavan

Reputation: 997

You can see the outer loop iterates (n-4) times, since it is starting with 4 and condition is less than only. The inner loop will iterate maximum of 4 times. Because it starts with i-3 and ends in i. So the complexity is 4*(n-4). Hence the complexity is O(n).

Upvotes: 10

Related Questions