Algorithmic complexity of this nested loop

Question

Is it O(n) or O(n*logn) of the code below:

for(int j=n, int sum = 0; j>0 ; j--) 
    for(int k=j; k >0; k--) sum++;

List of iterations:

j = 5: k = 5, 4, 3, 2, 1
j = 4: k = 4, 3, 2, 1,
j = 3: k = 3, 2, 1
j = 2: k = 2, 1
j = 1: k = 1

We have 15 iterations in total. But, if it is O(n), then only 5 iterations must be.

And if it is O(n*logn) answer would be only around 11-12 iterations.

That's not how Big O works. You can't look at the number of iterations for a specific n and determine the algorithmic complexity, you need to analyze the number of iterations for general values of n. — interjay
– interjay, Commented Dec 19, 2016 at 9:14
The world isn't just made of O(n) and O(n Log n) algorithms ! — user1196549
– user1196549, Commented Dec 19, 2016 at 9:27
@John I believe that Yves Daoust already knows the area of the triangle :) — xenteros
– xenteros, Commented Dec 24, 2016 at 13:26

xenteros · Accepted Answer · 2016-12-19 09:25:25Z

7

It's O(n^2). Why? Well it takes:

Look, that for n = 5 the number of calculations i 15 in deed. On the other hand, for n=100 it will be 5050. Which is far away from 100log100 which is around 460.

According to Wikipedia:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann-Landau notation or asymptotic notation.

edited Dec 19, 2016 at 9:25

answered Dec 19, 2016 at 9:17

xenteros

15.9k12 gold badges59 silver badges93 bronze badges

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

Collectives™ on Stack Overflow

Algorithmic complexity of this nested loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related