Sorry if this question has already been asked, I wasn't sure how to search for it.
Say you have the following loop
for (i=0; i < n; i++)
for(j = i; j < n; j++)
Would this be O(n^2) or O(nlog(n)) and why?
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
回答1:
The outer loop's runtime (by itself) is O(n), and the inner loop's runtime is O(n-i). So the loop's time would be (n)(n-i), and when you throw away the constant i, the runtime would be O(n^2).
回答2:
The outer loop's run time is O(n), and the inner loop's run time is O(n-i). So the loop's time would be (n)(n-i), and when you throw away the constant i, the run time would be N*N=O(N^2 .
