{"id":22463,"date":"2020-09-11T06:55:36","date_gmt":"2020-09-11T13:55:36","guid":{"rendered":"https:\/\/careerkarma.com\/blog\/?p=22463"},"modified":"2020-12-29T10:57:03","modified_gmt":"2020-12-29T18:57:03","slug":"big-o-notation-space","status":"publish","type":"post","link":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/","title":{"rendered":"Big O Notation, Part Two: Space Complexity"},"content":{"rendered":"\n<p><strong>Note<\/strong>: If you haven\u2019t read our article on <a href=\"https:\/\/careerkarma.com\/blog\/big-o-notation-time\/\">time complexity<\/a>, it\u2019s recommended to start there. Part two of this series assumes you are familiar with different possible Big O values.<br><\/p>\n\n\n\n<p>In our first article about Big O Notation and <a href=\"https:\/\/careerkarma.com\/blog\/big-o-notation-time\/\">time complexity<\/a>, we talk about how much time it takes for the algorithm to complete when its input increases. This is important when we interact with very large datasets. A large dataset combined with a decent time complexity leads to more efficient algorithms. However, there is one more aspect to Big O Notation that needs to be considered: space complexity.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">What is Space Complexity?<\/h2>\n\n\n\n<p>Time complexity and space complexity are similar as they relate to the amount of input an algorithm has. Where time complexity is related to the amount of operations an algorithm needs to perform to terminate, space complexity is related to the total amount of space needed to complete the algorithm. Space complexity is expressed in terms of Big O Notation.&nbsp;<br><\/p>\n\n\n\n<p>The space complexity includes the amount of space needed for the input as well as the auxiliary space needed in the algorithm to execute. Auxiliary space is the extra space used to store temporary data structures or variables used to solve the algorithm. Just like in time complexity, the Big O of an algorithm considers the worst case scenario, or the asymptotic upper bound.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Figuring Out the Space Required to Run an Algorithm<\/h2>\n\n\n\n<p>When we figure out the space complexity of an algorithm, take a look at two things: the input size and the auxiliary space needed to run the function. In most cases, we don\u2019t reduce the size down to how many bytes the input is \u2013 we just look at the amount of memory the input or auxiliary space needs to use.&nbsp;<br><\/p>\n\n\n\n<p>The input of an algorithm is what gets passed into the function when it is invoked. Typically, this will be some sort of primitive value: string, number, or object. The exact size of each might differ based on language, but we can figure in a general sense how much space is needed.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example with Simple Inputs and Output<\/h3>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre>public int subtract(int a, int b) {\n   return a - b;\n}\n<\/pre><\/div>\n\n\n\n<p>(<strong>Note<\/strong>: We are using Java here so you can easily discern the data types, but this can pretty much go for any language.)<br><\/p>\n\n\n\n<p>Take the above function. The purpose of this function is to take an input \u2013 in this case two ints<em> <\/em>(short for integers) and return an output, also an int.&nbsp;<br><\/p>\n\n\n\n<p>In our input, we have two variables \u2013 int a and int b. Our returned value \u2013 an int \u2013 also takes up space as well. Because our integers are only evaluated once, we consider the space complexity here to be O(1) &#8211; constant time.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example with More Complex Input<\/h3>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre>public int sumArray(int[] array) {\n   int size = 0;\n   int sum = 0;\n   for (int i = 0; i &lt; size; i++) {\n       sum += array[i];\n   }\n   return sum;\n}\n<\/pre><\/div>\n\n\n\n<p>This function has an array as its input. The array, not knowing the length, has n indices. The two variables in the first two lines of the function are O(1) since they are evaluated only once. The sum is an integer, is also O(1). The Big O for space complexity is O(n) to dictate the space for the array.&nbsp;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The most efficient algorithm is one that takes the least amount of time and memory. It will be near impossible, if not impossible, though, to write an algorithm that will be able to satisfy both conditions. You ultimately have to sacrifice one for the other. The question becomes, which do you sacrifice?<br><\/p>\n\n\n\n<p>The answer is: it depends. Everything depends on the requirements for the project or algorithm you are working on. If you only have minimal memory, you need to sacrifice time complexity to use the least space and vice versa. <br><\/p>\n","protected":false},"excerpt":{"rendered":"Note: If you haven\u2019t read our article on time complexity, it\u2019s recommended to start there. Part two of this series assumes you are familiar with different possible Big O values. In our first article about Big O Notation and time complexity, we talk about how much time it takes for the algorithm to complete when&hellip;","protected":false},"author":77,"featured_media":22464,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[18070],"tags":[],"class_list":{"0":"post-22463","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-software-engineering-skills"},"acf":{"post_sub_title":"","sprint_id":"","query_class":"Software Engineering","school_sft":"","parent_sft":"","school_privacy_policy":"","has_review":null,"is_sponser_post":"","is_guest_post":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v27.4 (Yoast SEO v27.4) - https:\/\/yoast.com\/product\/yoast-seo-premium-wordpress\/ -->\n<title>Big O Notation, Part Two: Space Complexity | Career Karma<\/title>\n<meta name=\"description\" content=\"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Big O Notation, Part Two: Space Complexity\" \/>\n<meta property=\"og:description\" content=\"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma\" \/>\n<meta property=\"og:url\" content=\"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/\" \/>\n<meta property=\"og:site_name\" content=\"Career Karma\" \/>\n<meta property=\"article:publisher\" content=\"http:\/\/facebook.com\/careerkarmaapp\" \/>\n<meta property=\"article:published_time\" content=\"2020-09-11T13:55:36+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-12-29T18:57:03+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1020\" \/>\n\t<meta property=\"og:image:height\" content=\"680\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Christina Kopecky\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@career_karma\" \/>\n<meta name=\"twitter:site\" content=\"@career_karma\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Christina Kopecky\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/\"},\"author\":{\"name\":\"Christina Kopecky\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/#\\\/schema\\\/person\\\/ae0cdc4a5d198690d78482646894074e\"},\"headline\":\"Big O Notation, Part Two: Space Complexity\",\"datePublished\":\"2020-09-11T13:55:36+00:00\",\"dateModified\":\"2020-12-29T18:57:03+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/\"},\"wordCount\":619,\"commentCount\":0,\"image\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/09\\\/spacex-PIOgkhaF3WA-unsplash.jpg\",\"articleSection\":[\"Software Engineering\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/\",\"url\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/\",\"name\":\"Big O Notation, Part Two: Space Complexity | Career Karma\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/09\\\/spacex-PIOgkhaF3WA-unsplash.jpg\",\"datePublished\":\"2020-09-11T13:55:36+00:00\",\"dateModified\":\"2020-12-29T18:57:03+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/#\\\/schema\\\/person\\\/ae0cdc4a5d198690d78482646894074e\"},\"description\":\"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#primaryimage\",\"url\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/09\\\/spacex-PIOgkhaF3WA-unsplash.jpg\",\"contentUrl\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/09\\\/spacex-PIOgkhaF3WA-unsplash.jpg\",\"width\":1020,\"height\":680},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/big-o-notation-space\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Blog\",\"item\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Software Engineering\",\"item\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/software-engineering-skills\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Big O Notation, Part Two: Space Complexity\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/\",\"name\":\"Career Karma\",\"description\":\"Latest Coding Bootcamp News &amp; Career Hacks from Industry Insiders\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/#\\\/schema\\\/person\\\/ae0cdc4a5d198690d78482646894074e\",\"name\":\"Christina Kopecky\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/06\\\/image-3-150x150.jpg\",\"url\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/06\\\/image-3-150x150.jpg\",\"contentUrl\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/06\\\/image-3-150x150.jpg\",\"caption\":\"Christina Kopecky\"},\"description\":\"Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy, Repl.it, and Educative.\",\"sameAs\":[\"http:\\\/\\\/www.linkedin.com\\\/in\\\/cmvnk\"],\"url\":\"https:\\\/\\\/careerkarma.com\\\/blog\\\/author\\\/christina-kopecky\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Big O Notation, Part Two: Space Complexity | Career Karma","description":"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/","og_locale":"en_US","og_type":"article","og_title":"Big O Notation, Part Two: Space Complexity","og_description":"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma","og_url":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/","og_site_name":"Career Karma","article_publisher":"http:\/\/facebook.com\/careerkarmaapp","article_published_time":"2020-09-11T13:55:36+00:00","article_modified_time":"2020-12-29T18:57:03+00:00","og_image":[{"width":1020,"height":680,"url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg","type":"image\/jpeg"}],"author":"Christina Kopecky","twitter_card":"summary_large_image","twitter_creator":"@career_karma","twitter_site":"@career_karma","twitter_misc":{"Written by":"Christina Kopecky","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#article","isPartOf":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/"},"author":{"name":"Christina Kopecky","@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e"},"headline":"Big O Notation, Part Two: Space Complexity","datePublished":"2020-09-11T13:55:36+00:00","dateModified":"2020-12-29T18:57:03+00:00","mainEntityOfPage":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/"},"wordCount":619,"commentCount":0,"image":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#primaryimage"},"thumbnailUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg","articleSection":["Software Engineering"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/","url":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/","name":"Big O Notation, Part Two: Space Complexity | Career Karma","isPartOf":{"@id":"https:\/\/careerkarma.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#primaryimage"},"image":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#primaryimage"},"thumbnailUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg","datePublished":"2020-09-11T13:55:36+00:00","dateModified":"2020-12-29T18:57:03+00:00","author":{"@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e"},"description":"Space complexity is the other half of Big O Notation. Learn how to figure out space complexity at Career Karma","breadcrumb":{"@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/careerkarma.com\/blog\/big-o-notation-space\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#primaryimage","url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg","contentUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/09\/spacex-PIOgkhaF3WA-unsplash.jpg","width":1020,"height":680},{"@type":"BreadcrumbList","@id":"https:\/\/careerkarma.com\/blog\/big-o-notation-space\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog","item":"https:\/\/careerkarma.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Software Engineering","item":"https:\/\/careerkarma.com\/blog\/software-engineering-skills\/"},{"@type":"ListItem","position":3,"name":"Big O Notation, Part Two: Space Complexity"}]},{"@type":"WebSite","@id":"https:\/\/careerkarma.com\/blog\/#website","url":"https:\/\/careerkarma.com\/blog\/","name":"Career Karma","description":"Latest Coding Bootcamp News &amp; Career Hacks from Industry Insiders","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/careerkarma.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e","name":"Christina Kopecky","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg","url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg","contentUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg","caption":"Christina Kopecky"},"description":"Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy, Repl.it, and Educative.","sameAs":["http:\/\/www.linkedin.com\/in\/cmvnk"],"url":"https:\/\/careerkarma.com\/blog\/author\/christina-kopecky\/"}]}},"_links":{"self":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts\/22463","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/comments?post=22463"}],"version-history":[{"count":0,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts\/22463\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/media\/22464"}],"wp:attachment":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/media?parent=22463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/categories?post=22463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/tags?post=22463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}