What would be the time complexity of the following code snippet?

user_13997112 0
Viewed 91
int k = 0;
for (i = 0; k < n; i++){
    k = k + i;
}

I think that the time complexity of the above code should be O(n^2) as during the n(th) iteration, the value of k would be n(n + 1)/2, resulting in O(n^2) time complexity. Am I wrong here?

time-complexity
2 Answers

Let [i(t), k(t)] be the state at the loop condition of the iteration t.

i(0)=0, k(0)=0 and i(t+1) =i(t)+1; k(t+1) = k(t)+i(t)+1

Resolving i gives i(t)=t and k(t+1) = k(t)+t+1 is resolved to k(t)=t*(t+1)/2

Finding the time complexity is finding t from which k(t)>=n i.e t²+t>=2n i.e (t+1/2)²>=1/4 + 2n i.e t >= sqrt(1/4+2n) -1/2

So the complexity is O(sqrt(n))

user_42863250

This is a tricky one and I'm not sure* what the exact time complexity is, but I'll make a lazy approximation and provide the information I can establish.

k increases following the triangular number pattern: [0, 1, 3, 6, 10, 15, 21, 28, 36, 45...].

A k *= 2 pattern in the loop would be a classical example of a slow logarithmic growth rate.

However, because we're looking at a += rather than a *=, the growth increases faster than logarithmic.

On the other hand, += 1 would be classically linear, and this is growing much slower than that because the right-hand side variable increases triangularly per step.

Here's some code to help get a feel for the growth:

const fn = n => {
  let k = 0;

  for (var i = 0; k < n; i++) {
    k += i;
  }

  return i;
};

for (let n = 0; n < 12; n++) {
  console.log(
    `n=${10**n}, steps=${fn(10**n)}, log2=${Math.round(Math.log2(10**n))}`
  );
}

It's definitely not quadratic and somewhere between log and linear, closer to log.

* Update: Ahmed's sqrt(n) looks correct:

const fn = n => {
  let k = 0;

  for (var i = 0; k < n; i++) {
    k += i;
  }

  return i;
};

for (let n = 0; n < 12; n++) {
  console.log(
    `n=${10**n}, steps=${fn(10**n)}, sqrt=${Math.round(Math.sqrt(10**n))}`
  );
}

user_62433520
Related