{"id":446,"date":"2021-04-27T19:00:00","date_gmt":"2021-04-27T18:00:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/?p=446"},"modified":"2022-01-24T13:33:46","modified_gmt":"2022-01-24T13:33:46","slug":"time-complexity-whats-that","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/2021\/04\/27\/time-complexity-whats-that\/","title":{"rendered":"How to know the Time Complexity of an Algorithm?"},"content":{"rendered":"\n<p class=\"has-black-color has-text-color wp-block-paragraph\">If you ever took a programming module where you had to build an algorithm to compute something, you were most probably asked about its complexity. Well, if not, it&#8217;s a good practice to check if the algorithm you wrote is efficient. No one wants to have the programme running for hours if there are faster options to achieve similar results, am I right? A common way to evaluate the complexity of a model is using Big <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O} <\/span> notation. But what is it?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Big <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}<\/span> notation is a mathematical property used to describe the asymptotic behaviour of functions. It gives us information about how fast a function grows or declines. It has many applications and one of them is to analyse the cost of algorithms.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">If you are familiar with this notation applied to programming, you may know that the most common complexities are:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(1) <\/span><\/li><li><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(\\log(n)) <\/span><\/li><li><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n) <\/span><\/li><li><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n\\log(n)) <\/span><\/li><li><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n^2) <\/span><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">We can also have <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(2^n) <\/span> and <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n!) <\/span>, but these are not that common. Okay, so I have already listed the most frequent complexities, but how can we see which one is our algorithm?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"block-94f40269-cc28-47a4-bd46-4bc13eec8964\"><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(1) <\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">This seems the better one, right? Well, it is. In fact, independently of the input data size, say <span class=\"wp-katex-eq\" data-display=\"false\"> n <\/span>, the algorithm will take the same time running. So, for example, if the goal of your algorithm is simply to assess an element of an array, or just adding one element to a fixed size list, then it won&#8217;t depend on <span class=\"wp-katex-eq\" data-display=\"false\"> n<\/span>. Getting this complexity is the best you can aim for. Although, of course, in some cases (most of the cases, really), you won&#8217;t be able to get it. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"block-87088459-c26e-4ef6-aabc-3e26811f6201\"><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(\\log(n)) <\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">If your algorithm runs in a time proportional to the logarithm of the input data size, that is <span class=\"wp-katex-eq\" data-display=\"false\"> \\log(n) <\/span>, then you have <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(\\log(n)) <\/span> complexity. This type of complexity is usually present in algorithms that somehow divide the input size. One example is the <span style=\"color:#b7a99a\" class=\"has-inline-color\">Binary search technique<\/span>:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Assume that the data is already sorted. This method starts by selecting the median, say <span class=\"wp-katex-eq\" data-display=\"false\"> med <\/span>, and then compares this value with a target value (chosen <em>a priori<\/em>), say <span class=\"wp-katex-eq\" data-display=\"false\"> y <\/span>. It then has 3 options:<ol><li>If <span class=\"wp-katex-eq\" data-display=\"false\"> med = y<\/span>, then there was a success<\/li><li>If <span class=\"wp-katex-eq\" data-display=\"false\"> med &gt; y<\/span>, then it finds the median of the upper half of the data and compares it again with <span class=\"wp-katex-eq\" data-display=\"false\"> y<\/span><\/li><li>If <span class=\"wp-katex-eq\" data-display=\"false\"> med &lt; y<\/span>, then it searches for the median of the lower half of the data and performs the same comparison<\/li><\/ol><\/li><li>The algorithm stops when <span class=\"wp-katex-eq\" data-display=\"false\"> med = y<\/span> or until it&#8217;s impossible to split the data.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"block-87088459-c26e-4ef6-aabc-3e26811f6201\"><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n) <\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">This one is as straightforward as the <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(1)<\/span>. If the time taken to perform the algorithm grows linearly with the <span class=\"wp-katex-eq\" data-display=\"false\"> n<\/span>, then the complexity is of <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n)<\/span>. An example of an algorithm with this complexity is if we have a list and we want to search for its maximum. It will iterate over the <span class=\"wp-katex-eq\" data-display=\"false\"> n<\/span> elements of the list, storing the maximum found at each step.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"block-87088459-c26e-4ef6-aabc-3e26811f6201\"><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n\\log(n)) <\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">As in the <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(\\log(n))<\/span>, this complexity is typical of algorithms which divide the input data set. One example is the <span style=\"color:#b7a99a\" class=\"has-inline-color\">Merge sort technique<\/span>: briefly, it first divides a list into equal halves and then combines them in a sorted way. Consider a list of 4 unsorted elements, for example <span class=\"wp-katex-eq\" data-display=\"false\"> \\{3, 1, 2, 5\\} <\/span>. First, the data will be split into two lists of 2 elements, that is <span class=\"wp-katex-eq\" data-display=\"false\"> \\{3, 1\\} <\/span> and <span class=\"wp-katex-eq\" data-display=\"false\"> \\{2, 5\\} <\/span> and then these two lists will be divided into 4 lists of 1 element each, that is <span class=\"wp-katex-eq\" data-display=\"false\"> \\{3\\}, \\{1\\}, \\{2\\} <\/span> and <span class=\"wp-katex-eq\" data-display=\"false\"> \\{5\\} <\/span>. In the next step, the algorithm will sort the elements by the 4 last lists and combine them into two lists, that is <span class=\"wp-katex-eq\" data-display=\"false\"> \\{1, 3\\} <\/span> and <span class=\"wp-katex-eq\" data-display=\"false\"> \\{2, 5\\} <\/span>. The final step is to combine these two lists into one sorted, that is <span class=\"wp-katex-eq\" data-display=\"false\"> \\{1, 2, 3, 5\\} <\/span>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"block-87088459-c26e-4ef6-aabc-3e26811f6201\"><span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n^2) <\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The last complexity I&#8217;m going to talk about is the <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n^2) <\/span>. As you may have guessed based on the previous ones, this will happen if the algorithm runs in a time proportional to the square of the size of the input data set. This may happen if you have, for example, two nested loops iterating over <span class=\"wp-katex-eq\" data-display=\"false\"> n^2<\/span>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">These are not the only possibilities, but they are the most common to happen. You can have complexity of <span class=\"wp-katex-eq\" data-display=\"false\"> \\mathcal{O}(n^3) <\/span> if instead of two nested for loops, you have three, and so on. A very good way to evaluate the performance of your algorithm is by plotting the time it takes to run and then compare its shape with these common complexities. The following graph may be useful for that.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-content\/uploads\/sites\/22\/2021\/04\/1_KfZYFUT2OKfjekJlCeYvuQ.jpeg\" alt=\"\" class=\"wp-image-477\" width=\"571\" height=\"397\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-content\/uploads\/sites\/22\/2021\/04\/1_KfZYFUT2OKfjekJlCeYvuQ.jpeg 800w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-content\/uploads\/sites\/22\/2021\/04\/1_KfZYFUT2OKfjekJlCeYvuQ-300x209.jpeg 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-content\/uploads\/sites\/22\/2021\/04\/1_KfZYFUT2OKfjekJlCeYvuQ-768x534.jpeg 768w\" sizes=\"auto, (max-width: 571px) 100vw, 571px\" \/><figcaption>Image taken from <a href=\"https:\/\/www.bigocheatsheet.com\/\" data-type=\"URL\" data-id=\"https:\/\/www.bigocheatsheet.com\/\" target=\"_blank\" rel=\"noreferrer noopener\">here<\/a><\/figcaption><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">I hope you find this post interesting and useful. You can see more here:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.bigocheatsheet.com\/\" target=\"_blank\">https:\/\/www.bigocheatsheet.com\/<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/rob-bell.net\/2009\/06\/a-beginners-guide-to-big-o-notation\" target=\"_blank\">https:\/\/rob-bell.net\/2009\/06\/a-beginners-guide-to-big-o-notation<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.freecodecamp.org\/news\/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c\/\" target=\"_blank\">https:\/\/www.freecodecamp.org\/news\/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c\/<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/stackoverflow.com\/questions\/11032015\/how-to-find-time-complexity-of-an-algorithm\" target=\"_blank\">https:\/\/stackoverflow.com\/questions\/11032015\/how-to-find-time-complexity-of-an-algorithm<\/a><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Hope to see you soon!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>If you ever took a programming module where you had to build an algorithm to compute something, you were most probably asked about its complexity. Well,&#46;&#46;&#46;<\/p>\n","protected":false},"author":21,"featured_media":478,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[18,17],"class_list":["post-446","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-blog","tag-algorithm","tag-programming"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/posts\/446","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/comments?post=446"}],"version-history":[{"count":7,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/posts\/446\/revisions"}],"predecessor-version":[{"id":510,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/posts\/446\/revisions\/510"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/media\/478"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/media?parent=446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/categories?post=446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/wp-json\/wp\/v2\/tags?post=446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}