CODEWITHSUNDEEP
algorithmmathbig-ocomplexity-theory
DarkCat
DarkCat

Reputation: 1

Asymptotic complexity of an algorithm (Big - O)

I've got the following example:

i=2;
while i<=n {
   O(1)
   j=2*i
   while j<=n {
       O(1)
       j=j+i
   }
   i=i+1

I'm a beginner at calculating asymptotic complexity. I think it is O((n-1)*(n/4)) but I'm not sure if this answer is correct or I'm missing something.

Upvotes: 0

Views: 54

Answers (1)

user1196549
user1196549

Reputation:

In the inner loop, j goes from 2i to n in steps i, so the inner loop runs (n-2i)/i+1 times, which is n/i-1 (integer division).

Then the outer loop runs with i from 2 to n, for a total of n/2-1+n/3-1+n/4-1+...n/(n/2)-1 inner iterations (for larger i, there are no iterations).

This quantity is difficult to estimate, but is bounded above by n (H(n/2)-1)-n/2 where H denotes an Harmonic Number.

We know that Hn~O(log n), hence, asymptotically, the running time is O(n log n).

Upvotes: 2

Related Questions