{"id":25028,"date":"2017-05-27T17:00:22","date_gmt":"2017-05-27T11:30:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25028"},"modified":"2017-05-27T17:00:22","modified_gmt":"2017-05-27T11:30:22","slug":"a-time-complexity-question","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/a-time-complexity-question\/","title":{"rendered":"A Time Complexity Question"},"content":{"rendered":"<p>What is a\u00a0time complexity of following function fun()? Assume that log(x) returns log value in base 2.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dvoid%20fun()%0A%7B%0A%20%20%20int%20i%2C%20j%3B%0A%20%20%20for%20(i%3D1%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(j%3D1%3B%20j%3C%3Dlog(i)%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20printf(%22GeeksforGeeks%22)%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><a href=\"https:\/\/www.wikitechy.com\/technology\/time-complexity-of-building-a-heap\/\">Time Complexity<\/a> of the above function can be written as \u0398(log 1) + \u0398(log 2) + \u0398(log 3) + . . . . + \u0398(log n) which is \u0398 (log n!)<\/p>\n<p>Order of growth of \u2018log n!\u2019 and \u2018n log n\u2019 is same for large values of n, i.e., \u0398 (log n!) = \u0398(n log n). So time complexity of fun() is \u0398(n log n).<\/p>\n<p>The expression <strong>\u0398(log n!) = \u0398(n log n)<\/strong> can be easily derived from following Stirling\u2019s approximation (or Stirling\u2019s formula).<\/p>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201dc\u201d manual=\u201d%20%20%20log%20n!%20%3D%20n%20log%20n%20-%20n%20%2B%20O(log(n))%20\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n","protected":false},"excerpt":{"rendered":"<p>A Time Complexity Question &#8211; Analysis of Algorithm What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.<\/p>\n","protected":false},"author":1,"featured_media":25304,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70146],"tags":[70250,71745,71750,71749,71748,70526,70523,70036,70022,70528,70139,71747,70032,70529,71493,70037,70142,71744,71746,70553,70450],"class_list":["post-25028","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-analysis-of-algorithm","tag-algorithm-complexity","tag-gate-questions-on-time-complexity","tag-problems-on-time-complexity-in-data-structure","tag-problems-on-time-complexity-of-algorithms","tag-quiz-on-time-complexity","tag-space-complexity-of-a-program","tag-time-and-space-complexity","tag-time-and-space-complexity-of-algorithms","tag-time-complexity","tag-time-complexity-and-space-complexity","tag-time-complexity-examples","tag-time-complexity-exercises","tag-time-complexity-in-data-structure","tag-time-complexity-of-algorithms","tag-time-complexity-of-algorithms-examples","tag-time-complexity-of-all-sorting-algorithms","tag-time-complexity-of-an-algorithm","tag-time-complexity-practice-problems","tag-time-complexity-problems-and-solutions","tag-what-is-time-complexity","tag-worst-case-complexity"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25028","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=25028"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25028\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25304"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25028"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25028"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25028"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}