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 !!
1 Like
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)?
@Munim_Iftikhar
Well, using your argument that it is totally ok to simplify N + log_2(N) to O(n) for j < var check. Shouldn’t authors simplify all N+1 estimates for loop checks across the course to just N, then? Where is the consistency in arbitrarily simplifying expressions in some places, but not the others?
As to your question - if you use N + log(N) for j < var check instead of current N, then you’ll arrive to total running time complexity of 7 + 4n + 3logn.