CODEWITHSUNDEEP
algorithmc++11time-complexitybig-o
oneturkmen
oneturkmen

Reputation: 1330

Algorithmic complexity of this nested loop

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.

Upvotes: 2

Views: 112

Answers (1)

xenteros
xenteros

Reputation: 15842

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

enter image description here

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.

Upvotes: 7

Related Questions