{"id":31145,"date":"2023-01-19T17:24:47","date_gmt":"2023-01-19T11:54:47","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/"},"modified":"2023-01-19T17:24:47","modified_gmt":"2023-01-19T11:54:47","slug":"solved-what-will-be-the-big-o-notation-for-this-code","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/","title":{"rendered":"[Solved] What will be the big-O notation for this code?"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

The way I see it, your code would<\/em> be O(n) if it wasn\u2019t for the a.pop(0)<\/code> part. Since lists are implemented as arrays in memory, removing an element at the top means that all elements in the array need to moved as well. So removing from a list is O(n)<\/a>. You do that in a loop over j<\/code> and as far as I can tell, in the end, the sum of all j<\/code>s will be the same as n<\/code>, so you are removing the item n<\/code> times from the list, making this part quadratic (O(n\u00b2)).<\/p>\n

You can avoid this though by not modifying your list, and just keeping track of the initial index. This not only removes the need for the pop, but also the loop over j<\/code>, making the complexity calculation a bit more straight-forward:<\/p>\n

final_count = 0\noffset = 0\nwhile n > 1:\n    i = 0\n    j = 1\n    while a[offset + i + 1] == a[offset + i]:\n        i += 1\n        j += 1\n        if i == n - 1:\n            break\n\n    offset += j\n    final_count += j * (n - j)\n    n = n - j\n<\/code><\/pre>\n
Btw. it\u2019s not exactly clear to me why you keep track of j<\/code>, since j = i + 1<\/code> at every time, so you can get rid of that, making the code a bit simpler. And at the very end j * (n - j)<\/code> is exactly j * n<\/code> if you first<\/em> adjust n<\/code>:<\/p>\n
final_count = 0\noffset = 0\nwhile n > 1:\n    i = 0\n    while a[offset + i + 1] == a[offset + i]:\n        i += 1\n        if i == n - 1:\n            break\n\n    offset += i + 1\n    n = n - (i + 1)\n    final_count += (i + 1) * n\n<\/code><\/pre>\n
One final note: As you may notice, offset<\/code> is now counting from zero to the length of your list, while n<\/code> is doing the reverse, counting from the length of your list to zero. You could probably combine this, so you don\u2019t need both.<\/p>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            1<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved What will be the big-O notation for this code? <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] The way I see it, your code would be O(n) if it wasn\u2019t for the a.pop(0) part. Since lists are implemented as arrays in memory, removing an element at the top means that all elements in the array need to moved as well. So removing from a list is O(n). You do that in … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,349,1238],"class_list":["post-31145","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-python","tag-time-complexity"],"yoast_head":"\n[Solved] What will be the big-O notation for this code? - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] What will be the big-O notation for this code? - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The way I see it, your code would be O(n) if it wasn\u2019t for the a.pop(0) part. Since lists are implemented as arrays in memory, removing an element at the top means that all elements in the array need to moved as well. So removing from a list is O(n). You do that in ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2023-01-19T11:54:47+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] What will be the big-O notation for this code?\",\"datePublished\":\"2023-01-19T11:54:47+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\"},\"wordCount\":241,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"python\",\"time-complexity\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\",\"name\":\"[Solved] What will be the big-O notation for this code? - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2023-01-19T11:54:47+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] What will be the big-O notation for this code?\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] What will be the big-O notation for this code? - JassWeb","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:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] What will be the big-O notation for this code? - JassWeb","og_description":"[ad_1] The way I see it, your code would be O(n) if it wasn\u2019t for the a.pop(0) part. Since lists are implemented as arrays in memory, removing an element at the top means that all elements in the array need to moved as well. So removing from a list is O(n). You do that in ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/","og_site_name":"JassWeb","article_published_time":"2023-01-19T11:54:47+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] What will be the big-O notation for this code?","datePublished":"2023-01-19T11:54:47+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/"},"wordCount":241,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","python","time-complexity"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/","url":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/","name":"[Solved] What will be the big-O notation for this code? - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2023-01-19T11:54:47+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-what-will-be-the-big-o-notation-for-this-code\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] What will be the big-O notation for this code?"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/31145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=31145"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/31145\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=31145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=31145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=31145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}