World's most popular travel blog for travel bloggers.

The complexity of the algorithm with loops

, , No Comments
Problem Detail: 

I have algorithm that contains next loops:

for (int i = 0; i < size; ++i) {      for (int j = i + 1; j < size; ++j) {         //Do stuff     } } 

I found that this algorithm has $O(n^2)$ complexity but I can't understand why? I.e. if $N = 4$ then $n^2 = 16$ but my loop has 6 iterations only. Just it's a half of $n^2$ value.

P.S. I understand never how to measure the complexity of the algorithm, I only can understand how to write it in the mathematics.

Asked By : Шах
Answered By : rcpinto

Your "stuff" will get executed $N(N - 1)/2 = 0.5N^2 - 0.5N$ times. When analyzing the asymptotic complexity, only the highest order term is kept, and multiplicative constants are removed, leaving you with $O(N^2)$.

It works this way because we're interested in what happens when $N$ goes to infinity (scalability).

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback