{"id":24961,"date":"2017-05-30T17:56:22","date_gmt":"2017-05-30T12:26:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24961"},"modified":"2017-05-30T18:00:27","modified_gmt":"2017-05-30T12:30:27","slug":"analysis-of-loops","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/analysis-of-loops\/","title":{"rendered":"Analysis of Loops"},"content":{"rendered":"

1) O(1)<\/strong>: Time complexity of a function (or set of statements) is considered as O(1) if it doesn\u2019t contain Analysis of Loops, recursion and call to any other non-constant time function.<\/p>\n

\/\/ set of non-recursive and non-loop statements<\/pre>\n
For example swap() function has O(1) time complexity.<\/p>\n[ad type=”banner”]\n
A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1).<\/p>\n
 \/\/ Here c is a constant \r\n for (int i = 1; i <= c; i++) { \r\n \/\/ some O(1) expressions\r\n }<\/pre>\n
2) O(n):<\/strong> Time Complexity of a loop is considered as O(n) if the loop variables is incremented \/ decremented by a constant amount. For example following functions have O(n) time complexity.<\/p>\n
\/\/ Here c is a positive integer constant \r\n for (int i = 1; i <= n; i += c) { \r\n \/\/ some O(1) expressions\r\n }\r\n\r\nfor (int i = n; i > 0; i -= c) {\r\n \/\/ some O(1) expressions\r\n }<\/pre>\n[ad type=”banner”]\n
3) O(nc<\/sup>)<\/strong>: Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n2<\/sup>) time complexity<\/p>\n
\r\n for (int i = 1; i <=n; i += c) {\r\n for (int j = 1; j <=n; j += c) {\r\n \/\/ some O(1) expressions\r\n }\r\n }\r\n\r\nfor (int i = n; i > 0; i += c) {\r\n for (int j = i+1; j <=n; j += c) {\r\n \/\/ some O(1) expressions\r\n }<\/pre>\n
For example Selection sort and Insertion Sort have O(n2) time complexity.<\/p>\n
4) O(Logn)<\/strong>\u00a0:Time Complexity of a loop is considered as O(Logn) if the loop variables is divided\/ multiplied by a constant amount.<\/p>\n
 for (int i = 1; i <=n; i *= c) {\r\n \/\/ some O(1) expressions\r\n }\r\n for (int i = n; i > 0; i \/= c) {\r\n \/\/ some O(1) expressions\r\n }<\/pre>\n
For example Binary Search(refer iterative implementation) has O(Logn) time complexity.<\/p>\n
5) O(LogLogn)<\/strong>\u00a0:<\/a>Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced \/ increased exponentially by a constant amount.<\/p>\n
\/\/ Here c is a constant greater than 1 \r\n for (int i = 2; i <=n; i = pow(i, c)) { \r\n \/\/ some O(1) expressions\r\n }\r\n \/\/Here fun is sqrt or cuberoot or any other constant root\r\n for (int i = n; i > 0; i = fun(i)) { \r\n \/\/ some O(1) expressions\r\n }<\/pre>\n[ad type=”banner”]\n
How to combine time complexities of consecutive loops?<\/strong><\/p>\n
When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.<\/p>\n
for (int i = 1; i <=m; i += c) { \r\n \/\/ some O(1) expressions\r\n }\r\n for (int i = 1; i <=n; i += c) {\r\n \/\/ some O(1) expressions\r\n }\r\n Time complexity of above code is O(m) + O(n) which is O(m+n)\r\n If m == n, the time complexity becomes O(2n) which is O(n).<\/pre>\n
How to calculate time complexity when there are many if, else statements inside loops?<\/strong><\/p>\n
As discussed here, worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case. We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.<\/p>\n
For example consider the linear search function where we consider the case when element is present at the end or not present at all.<\/p>\n
When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.<\/p>\n
How to calculate time complexity of recursive functions?<\/strong><\/p>\n
Time complexity of a recursive function can be written as a mathematical recurrence relation. To calculate time complexity, we must know how to solve recurrences. We will soon be discussing recurrence solving techniques as a separate post.<\/p>\n","protected":false},"excerpt":{"rendered":"
Analysis of Loops – Analysis of Algorithm – O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn\u2019t contain Analysis.<\/p>\n","protected":false},"author":1,"featured_media":26049,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70146],"tags":[71490,70027,70246,70234,71680,70558,71489,71679,71684,71682,71683,71681,71491,71607,70257,71678,70259,70240],"class_list":["post-24961","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-analysis-of-algorithm","tag-complexity-of-3-nested-for-loops","tag-complexity-of-algorithm","tag-design-analysis-and-algorithm","tag-design-and-analysis-of-algorithms","tag-for-loop-algorithm-in-c","tag-how-to-calculate-time-complexity-for-a-given-algorithm","tag-how-to-find-time-complexity-of-for-loop","tag-how-to-write-algorithm-for-for-loop","tag-kirchhoffs-voltage-law","tag-mesh-analysis","tag-nodal","tag-nodal-analysis","tag-questions-on-time-complexity-of-algorithms","tag-space-complexity-of-an-algorithm","tag-time-complexity-of-selection-sort","tag-time-complexity-of-while-loop","tag-types-of-algorithm","tag-what-is-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24961","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=24961"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24961\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/26049"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24961"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24961"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}