{"id":17133,"date":"2024-03-19T11:30:07","date_gmt":"2024-03-19T11:30:07","guid":{"rendered":"http:\/\/www.max-sperling.bplaced.net\/?p=17133"},"modified":"2024-03-19T13:55:01","modified_gmt":"2024-03-19T13:55:01","slug":"computational-complexity-examples","status":"publish","type":"post","link":"http:\/\/www.max-sperling.bplaced.net\/?p=17133","title":{"rendered":"Computational complexity &#8211; Examples"},"content":{"rendered":"<p><strong>Easy<\/strong><\/p>\n<details>\n<summary>\u25bc calcSum<\/summary>\n<p><u>Algorithm<\/u><\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\nvoid calcSum(int[] array)\r\n{\r\n    int sum = 0;\r\n\r\n    for (int i = 0; i &lt; array.length; ++i)\r\n    {\r\n        sum += array[i];\r\n    }\r\n}\r\n<\/pre>\n<p><u>Solution<\/u><br \/>\n&#8211; Analysis: L3: \u0398(1), L5: \u0398(n), L7: \u0398(1)<br \/>\n&#8211; Calculation: \u0398(1) + \u0398(n) * \u0398(1) = \u0398(n)<\/p>\n<\/details>\n<details>\n<summary>\u25bc calcSumAndProd<\/summary>\n<p><u>Algorithm<\/u><\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\nvoid calcSumAndProd(int[] array)\r\n{\r\n    int sum = 0;\r\n    int prod = 0;\r\n\r\n    for (int i = 0; i &lt; array.length; ++i)\r\n    {\r\n        sum += array[i];\r\n    }\r\n\r\n    for (int i = 0; i &lt; array.length; ++i)\r\n    {\r\n        prod = (prod == 0 ? prod + array[i] : prod * array[i]);\r\n    }\r\n}\r\n<\/pre>\n<p><u>Solution<\/u><br \/>\n&#8211; Analysis: L3: \u0398(1), L4: \u0398(1), L6: \u0398(n), L8: \u0398(1), L11: \u0398(n), L13: \u0398(1)<br \/>\n&#8211; Calculation: \u0398(1) + \u0398(1) + \u0398(n) * \u0398(1) + \u0398(n) * \u0398(1) = \u0398(2n) = \u0398(n)<\/p>\n<\/details>\n<details>\n<summary>\u25bc printCartProd<\/summary>\n<p><u>Algorithm<\/u><\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\nvoid printCartProd(int[] array)\r\n{\r\n    for (int i = 0; i &lt; array.length; ++i)\r\n    {\r\n        for (int j = 0; j &lt; array.length; ++j)\r\n        {\r\n            println(array[i] + &quot;,&quot; + array[j]);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p><u>Solution<\/u><br \/>\n&#8211; Analysis: L3: \u0398(n), L5: \u0398(n), L7: \u0398(1)<br \/>\n&#8211; Calculation: \u0398(n) * \u0398(n) * \u0398(1) = \u0398(n<sup>2<\/sup>)<\/p>\n<\/details>\n<hr>\n<p><strong>Moderate<\/strong><\/p>\n<details>\n<summary>\u25bc binarySearch<\/summary>\n<p><u>Algorithm<\/u><\/p>\n<pre class=\"brush: plain; title: ; notranslate\" title=\"\">\r\nint binarySearch(int[] sortedArray, int low, int high, int goal)\r\n{\r\n    if (low &lt;= high)\r\n    {\r\n        int mid = low + (high - low) \/ 2;\r\n \r\n        if (goal == sortedArray[mid]) {\r\n            return mid;\r\n        }\r\n        else if (goal &lt; sortedArray[mid]) {\r\n            return binarySearch(sortedArray, low, mid - 1, goal);\r\n        } else {\r\n            return binarySearch(sortedArray, mid + 1, high, goal);\r\n        }\r\n    }\r\n\r\n    return -1;\r\n}\r\n<\/pre>\n<p><u>Solution<\/u><br \/>\nBest case: First check is successful. \u2192 Goal is in the mid of the tree.<br \/>\n&#8211; Calculation: \u0398(1)<\/p>\n<p>Worst case: Last check is successful. \u2192 Goal is not in the tree at all.<br \/>\n&#8211; Calculation: \u0398(depth) = \u0398(log(n))<\/p>\n<\/details>\n","protected":false},"excerpt":{"rendered":"<p>Easy \u25bc calcSum Algorithm Solution &#8211; Analysis: L3: \u0398(1), L5: \u0398(n), L7: \u0398(1) &#8211; Calculation: \u0398(1) + \u0398(n) * \u0398(1)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[81],"tags":[],"_links":{"self":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17133"}],"collection":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17133"}],"version-history":[{"count":33,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17133\/revisions"}],"predecessor-version":[{"id":17166,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17133\/revisions\/17166"}],"wp:attachment":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17133"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}