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

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -