{"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":"<p>What is the Time Complexity of Loop with Powers with below function?<\/p>\n[ad type=&#8221;banner&#8221;]\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">void fun(int n, int k)<br\/>{<br\/>    for (int i=1; i&lt;=n; i++)<br\/>    {<br\/>      int p = pow(i, k); <br\/>      for (int j=1; j&lt;=p; j++)<br\/>      {<br\/>          \/\/ Some O(1) work<br\/>      }<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p><a href=\"https:\/\/www.wikitechy.com\/technology\/analysis-of-loops\/\">Time complexity<\/a> of above function can be written as 1<sup>k<\/sup> + 2<sup>k<\/sup> + 3<sup>k<\/sup> + \u2026 n1<sup>k<\/sup>.<\/p>\n<p>Let us try few examples:<\/p>\n[ad type=&#8221;banner&#8221;]\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">k=1<br\/>Sum = 1 + 2 + 3 ... n <br\/>    = n(n+1)\/2 <br\/>    = n2 + n\/2<br\/><br\/>k=2<br\/>Sum = 12 + 22 + 32 + ... n12.<br\/>    = n(n+1)(2n+1)\/6<br\/>    = n3\/3 + n2\/2 + n\/6<br\/><br\/>k=3<br\/>Sum = 13 + 23 + 33 + ... n13.<br\/>    = n2(n+1)2\/4<br\/>    = n4\/4 + n3\/2 + n2\/4   <\/code><\/pre> <\/div>\n<p>In general, asymptotic value can be written as <strong>(n<sup>k+1<\/sup>)\/(k+1) + \u0398(n<sup>k<\/sup>)<\/strong><\/p>\n<p>Note that, in asymptotic notations like <strong>\u0398<\/strong> we can always ignore lower order terms. So the time complexity is <strong>\u0398(n<sup>k+1<\/sup> \/ (k+1))<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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}]}}