Time Complexity Analysis - Double Loop - Second increments by 0.01

Question

What is the time complexity of the following program?

---

for (int j = 1 to n) {
  int k = j
  while (k < n) {
    Sum += a[k]*b[k]
    k += 0.01 * n
  }
}

Answer 1

When n < 100, because k is an integer, it is obvious that inner loop is an infinite loop.

When n >= 100, as step increasement of k is %1 of n, the inner loop will never runs more than 100  times for each j. Thus the total running count is less than 100 * n. More specifically, this total running count equals 0.5*100*n (for boarder condition is k<n and n may not be a multiplier of 100, it is not strictly equals to that).

So the time-complexity should be O(n).

The experiment shows that the total running count is linear to n, and complies with the theory of total count = 0.5*100*n.

Comments

Hi I agree with your second part, but I don't think there's anything special for n<100 nor when n is not multiplier of 100.

---

Is it when 0.01*k is not an integer there will be infinite time counting Sum += a[k]*b[k]?

---

well, I mean, when you declare k as an integer, in most programming language, you can add a float to k, say "k=k+f ;" where f is a float or double, let's say f=0.1 for good. The result in math should be k=1.1, but here k is an integer, so the system will apply a convert action like "k=(int)(k+f)", so when abs(f)<1, k keep unchanged.
It is only meaningful in practice when you run this program in some actual language, like in Java. If you mean in pure theory discussion, there is no such problem, n<100 will not cause any trouble.

---

Oh I see the problem is the declaration of k as an integer! THX dude.

Answer 2

It seems to be simply O(n).