{"id":25059,"date":"2017-05-27T17:25:25","date_gmt":"2017-05-27T11:55:25","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25059"},"modified":"2017-05-27T17:25:25","modified_gmt":"2017-05-27T11:55:25","slug":"time-complexity-of-loop-with-powers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/time-complexity-of-loop-with-powers\/","title":{"rendered":"Time Complexity of Loop with Powers"},"content":{"rendered":"

What is the Time Complexity of Loop with Powers with below function?<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201dvoid%20fun(int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20for%20(int%20i%3D1%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20int%20p%20%3D%20pow(i%2C%20k)%3B%20%0A%20%20%20%20%20%20for%20(int%20j%3D1%3B%20j%3C%3Dp%3B%20j%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20Some%20O(1)%20work%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time complexity<\/a> of above function can be written as 1k<\/sup> + 2k<\/sup> + 3k<\/sup> + \u2026 n1k<\/sup>.<\/p>\n

Let us try few examples:<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201dk%3D1%0ASum%20%3D%201%20%2B%202%20%2B%203%20\u2026%20n%20%0A%20%20%20%20%3D%20n(n%2B1)%2F2%20%0A%20%20%20%20%3D%20n2%20%2B%20n%2F2%0A%0Ak%3D2%0ASum%20%3D%2012%20%2B%2022%20%2B%2032%20%2B%20\u2026%20n12.%0A%20%20%20%20%3D%20n(n%2B1)(2n%2B1)%2F6%0A%20%20%20%20%3D%20n3%2F3%20%2B%20n2%2F2%20%2B%20n%2F6%0A%0Ak%3D3%0ASum%20%3D%2013%20%2B%2023%20%2B%2033%20%2B%20\u2026%20n13.%0A%20%20%20%20%3D%20n2(n%2B1)2%2F4%0A%20%20%20%20%3D%20n4%2F4%20%2B%20n3%2F2%20%2B%20n2%2F4%20%20%20\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

In general, asymptotic value can be written as (nk+1<\/sup>)\/(k+1) + \u0398(nk<\/sup>)<\/strong><\/p>\n

Note that, in asymptotic notations like \u0398<\/strong> we can always ignore lower order terms. So the time complexity is \u0398(nk+1<\/sup> \/ (k+1))<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"

Time Complexity of Loop with Powers- Analysis of Algorithm What is the time complexity of below function?Time complexity of above function can be written as<\/p>\n","protected":false},"author":1,"featured_media":25328,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70146],"tags":[70245,69992,70710,70021,70719,70127,70007,70138,70711,70126,70140,70255,70253,70009,71490,70027,70033,70041,70527,70559,70550,70558,70561,70720,71489,70125,71491,70541,70129,71494,70139,70529,71493,70142,70026,71492,70716,70143,70721,70986],"class_list":["post-25059","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-analysis-of-algorithm","tag-algorithm-analysis","tag-analysis-of-algorithms","tag-big-0","tag-big-o-notation","tag-big-o-notation-example-problems","tag-big-o-notation-examples","tag-big-o-notation-in-data-structure","tag-big-o-notation-tutorial","tag-big-oh","tag-big-oh-notation","tag-bigo-meaning","tag-calculate-time-complexity","tag-complexity-analysis","tag-complexity-in-data-structure","tag-complexity-of-3-nested-for-loops","tag-complexity-of-algorithm","tag-complexity-of-algorithm-in-data-structure","tag-complexity-of-all-sorting-algorithms","tag-complexity-of-an-algorithm","tag-how-to-calculate-space-complexity","tag-how-to-calculate-time-complexity","tag-how-to-calculate-time-complexity-for-a-given-algorithm","tag-how-to-calculate-time-complexity-of-a-program-in-c","tag-how-to-find-time-complexity","tag-how-to-find-time-complexity-of-for-loop","tag-o-notation","tag-questions-on-time-complexity-of-algorithms","tag-selection-sort-time-complexity","tag-small-o-notation","tag-time-complexity-calculator","tag-time-complexity-examples","tag-time-complexity-of-algorithms","tag-time-complexity-of-algorithms-examples","tag-time-complexity-of-an-algorithm","tag-time-complexity-of-binary-search","tag-time-complexity-of-nested-for-loops","tag-what-is-big-o-notation","tag-what-is-bigo","tag-what-is-complexity","tag-what-is-nested-loop"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25059","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25059"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25059\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25328"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}