big o - Big O - Time Complexity puzzling for while loops -
as time complexity example (refreshing mind) attempting solve find running time (in terms on n) of following algorithm:
for (i=1; <= n; i++) { //o(n) k = 1; (j=1; j <= i; j++) { //o(n) k = 2*k; } j = k*k; while (j > 1) { //o(..?) j = j / 2; } }
i understand first 2 loops combined take o(n^2), little perplexed @ how find running time of while loop. although know while loop runs twice first execution, 4 times, 6... multiples of 2. make run o(nlog(n)) times?
the repeated division log_2(j)
same log(j) / log(2)
. log(2)
constant, it's written log(j)
.
because o(log(n))
@ same depth o(n)
loop , o(n)
loop dwarfs o(log(n))
loop, 2 combined takes o(n)
time.
the final time complexity o(n^2)
.
Comments
Post a Comment