Finding the computational complexity of a nested loop

Question

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?

It's not quadratic (with respect to n) because j always goes from i-3 to i. That means the inner loop always only has four iterations, a number independent of n. — millimoose
– millimoose, Commented Sep 20, 2013 at 1:50
Also, there is a formula: wolframalpha.com/input/… - it's just not the same formula for every algorithm. — millimoose
– millimoose, Commented Sep 20, 2013 at 1:50

Ragavan · Accepted Answer · 2013-09-20 01:35:46Z

10

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).

answered Sep 20, 2013 at 1:35

Ragavan

9977 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

rullzing Over a year ago

Thanks for explaining. I got the inner lop part but I still didn't get why is the outer loop n-4? is it always going to be n-(the number of i) ?

Ragavan Over a year ago

Yes. The inner loop (not the block inside the inner loop) will get executed n-4 times, ie outer loop executes n-4 times.

Denim Datta Over a year ago

@rullzrullz : It's because the outer loop starts at 4 and ends at n. So (n-4) times

rullzing Over a year ago

Thank you very much for clarifying Ragavan and Panther

Pan Long · Accepted Answer · 2013-09-20 01:44:23Z

0

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)

answered Sep 20, 2013 at 1:44

Pan Long

1,0321 gold badge9 silver badges16 bronze badges

Collectives™ on Stack Overflow

Finding the computational complexity of a nested loop

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related