World's most popular travel blog for travel bloggers.

[Solved]: Running-time cost of Tweaked Nested Loop

, , No Comments
Problem Detail: 

I understand that the following nested for-loop:

for(i=0; i<n/2; i++)     for(j=0; j<n/2; j++)          print(j) 

has the runtime complexity of

which has a simplifed complexity of

but what is the resulting complexity of making j bound to i/2 in the inner loop? For instance:

for(i=0; i<n/2; i++)     for(j=0; j<i/2; j++)          print(j) 

Would this be


Asked By : TacoB0t

Answered By : vonbrand

The complexity would be

$$\sum_{i = 0}^{n/2-1} \sum_{j = 0}^{i/2-1} 1\,,$$ which is $O(n^2)$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback