educative.io

Educative

Wrong Calculation of Running Complexity

At this point of time I am losing it.
There are so many mistakes in this course and the moderators are not reverting back on the issues
How on earth the running complexity of while (j < var) would be just n ??
When the loop is entered shouldn’t this condition be checked again which will make it n+logn ??
and ultimate running time complexity should be 7 + 4n + 3logn !!

Hi Neeraj,

The Big-O notation of n+log(n) is O(n), which ultimately makes the time complexity of j < var equal to O(n).

Can you please elaborate on how the ultimate running time complexity is 7 + 4n + 3logn? That can help us to explain the problem more clearly.

Thank you!

Should it not be n*log(n) because there’s a while loop inside a for loop that results in a nested loop (multiply)?