CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Animeartist
Animeartist

Reputation: 1187

How to calculate the time complexity of nested loops?

How to calculate the time complexity of the following algorithm?

for(i=1;i<=n;i++)
  for(k=i;k*k<=n;k++)
   {
     Statements;
   }

From what I know, time complexity for nested for loops is equal to the number of times the innermost loop is executed. So here innermost loop is executed n*n times, hence it's O(n^2).

Could it be O(n) depending upon the condition k*k<=n given in the second loop?

Thank you!

Upvotes: 1

Views: 1551

Answers (1)

Berthur
Berthur

Reputation: 4495

Time complexity of an algorithm is always measured in terms of a certain type of operation. For example, if your Statements; have an un unknown time complexity which depends on n, then it would be misleading to describe the time complexity in the first place.

But what you are probably after is to know the time complexity in terms of Statements; operations. If Statements; is a constant-time operation, this becomes especially meaningful. And in this case, what we are looking for is simply to count how many times Statements; are executed. If this number is, say, 3*n, then the time complexity would be O(n).

To answer this question, let us break your nested loop apart. The outer loop iterates from (and including) 1 to n, so it will run exactly n times, regardless of anything.

For each iteration of the outer loop, the inner loop will execute once. It starts from k=i and iterates until k*k > n, or k > sqrt(n). Notice that whenever i > sqrt(n), it will not run at all. We can see that on average, it will run for

O(sqrt(n) + sqrt(n)-1 + sqrt(n)-2 + ... + 0) / n

iterations. By the summation formula you can find here, this equals

O( sqrt(n) * (sqrt(n) + 1) / 2 ) = O( (n + sqrt(n))/2 ) = O( n + sqrt(n) ) = O(n).

So yes, the time complexity in this case is O(n) as you suggested.

You can see this in action by writing a simple script which simulates your algorithm and counts the number of Statements;. Below in JavaScript, so it can be run as a snippet:

// Simulation
function f(n) {
  let res = 0;
  for(let i=1;i<=n;i++)
    for(let k=i;k*k<=n;k++)
      ++res;
  return res;
}

// Estimation
function g(n) {
  return ~~((n + Math.sqrt(n))/2);
}

console.log(
  f(10),
  f(100),
  f(1000),
  f(10000),
);
console.log(
  g(10),
  g(100),
  g(1000),
  g(10000),
);

I hope you found this useful.

Upvotes: 1

Related Questions