CODEWITHSUNDEEP
javaalgorithmtime-complexitylogarithm
Saad
Saad

Reputation: 1360

time complexity : why O(nlogn)?

I have a document that says the average case time-complexity for the given code is O(nlog2n)

Random r = new Random();
int k = 1 + r.nextInt(n);
for (int i = 0; i < n ; i += k);

I have computed the best and worst cases as:

Best case, k = n leading to time complexity of O(1).

Worst case, k = 1 leading to time complexity of O(n).

How can average case be O(nlog2n), which is higher than the worst case. Am I missing something?

Edit: The document could be prone to mistakes, so in that case what would be the average time-complexity of the above code, and why?

Upvotes: 4

Views: 185

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58300

For a given value of k, the for loop runs n/k times. (I'm ignoring rounding, which makes the analysis a bit more complicated but doesn't change the result).

Averaging over all values of k gives: (n/1 + n/2 + n/3 + ... + n/n) / n. That's the n'th harmonic number. The harmonic numbers tend to log(n).

Thus the average runtime complexity of this code is log(n). That's O(log n) or equivalently O(log_2 n).

Perhaps your book had an additional outer loop that ran this code n times?

Upvotes: 6

Related Questions