Time Complexity Analysis - 2 (2nd by log n)

Question

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

Answer 1

In this question the key point is that k will be increased by 1 everytime because of the for loop.

Then in the while loop K is increased by logn. n is the constant we set. We assume the time it runs in the while loop is t. So the while loop will run like 1+t*logn <= n, t = (n-1)/logn for the first time.

In the second time 2+t*logn <=n

so t <= (n-2)/logn

in the last time for the for loop, t<=(n-(n-1))/logn

sum of the t is (1+2+3+...(n-2)+(n-1))/logn = n(n-1)/2*logn = O(n²/logn)

also for all here is the question that how can i simplify O(n²/logn) further?

Hope i think it right

Comments

Thanks! I am on the same track with you, Jian. But is that O(n^2/logn) the final answer?
I mean I can't imagine how it grows. Or is there any transformation of n^2/logn?

---

I don't know, so I put my question in the last part waiting for Professor or some other students to answer lol. One of my thoughts is that I guessed for several functions g(n) like n^3 or n^2 and use limn->f(n)/g(n) // which here f(n) is n^2/logn to find the theta relations. But I failed to finish that.

---

O(n^2/log n) is the right answer.