Time Complexity of this double loop

Question

What will be the time complexity of this code?

 for(int i = 1 ; i <= b ; ++i )
     for(int j = i ; j <= b ; j += i )

something like b x b x ln(b): see the harmonic series.

Franck
– Franck

2016-10-30 18:35:08 +00:00
Commented Oct 30, 2016 at 18:35 — Franck
– Franck, Commented Oct 30, 2016 at 18:35

Community · Accepted Answer · 2017-05-23 12:33:18Z

8

You can expand the loops to something like this:

i = 1 ——>   1,2,3,…,b     b
i = 2 ——>   1,3,5,…,b     (b/2)
i = 3 ——>   1,4,7,…,b     (b/3)
i = 4 ——>   1,5,9,…,b     (b/4)
  …
i = b ——>   1, b          (b/b = 1)

This expands into a sum of the form:

b + b/2 + b/3 + … + b/b = b * (1 + 1/2 + 1/3 + … + 1/b)

You might recognize the second factor as the Harmonic Series. Then, using the result from the following SO answer: Finding Big O of the Harmonic Series you can get the Big Oh of your nested loops:

O(b * log(b))

edited May 23, 2017 at 12:33

CommunityBot

11 silver badge

answered Oct 30, 2016 at 18:43

Mike Dinescu

56k17 gold badges124 silver badges153 bronze badges

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

Collectives™ on Stack Overflow

Time Complexity of this double loop

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related