{"id":3178,"date":"2021-06-09T22:38:00","date_gmt":"2021-06-09T17:08:00","guid":{"rendered":"https:\/\/manorinfinity.com\/blog\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/"},"modified":"2021-06-09T22:38:00","modified_gmt":"2021-06-09T17:08:00","slug":"guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs","status":"publish","type":"post","link":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/","title":{"rendered":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS"},"content":{"rendered":"

Do you Know? In how many ways, you can express your algorithm? <\/span><\/span><\/p>\n

There are two ways to express your algorithms-<\/span><\/span><\/p>\n

<\/p>\n

1. Iterative Algorithms<\/span><\/span><\/h4>\n

2. Recursive Algorithms<\/span><\/span><\/h4>\n

Recursive algorithms can be converted into iterative algorithms and iterative algorithms can be converted into recursive algorithms, both have same in power.<\/span><\/span><\/p>\n

We will see the examples of both types of algorithm in further post.<\/span><\/span><\/p>\n

<\/span><\/span><\/p>\n

<\/a>
<\/span><\/span><\/p>\n

Guidelines for Asymptotic Notations:<\/span><\/span><\/h1>\n

So, there are some rules that you have to follow. These rules help us to determine the time complexity (running time) of the algorithm.<\/span><\/span><\/p>\n

1. <\/span>Non-Recursive and Non-Loop Statements:<\/span><\/span><\/h2>\n

If any algorithm doesn’t contain loop, recursion and call to any other non-constant time algorithm,<\/span> <\/span>then the time complexity of this type of algorithm is considered as <\/span>O(1)<\/span> or<\/span> linear time complexity<\/span>.<\/span><\/span><\/p>\n

Example 1-<\/span> <\/span>swap()<\/span> algorithm has <\/span>O(1)<\/span> time complexity.<\/span><\/span><\/p>\n

Example 2- <\/span>If a loop or recursion that runs a <\/span>constant<\/span> number of times. Then, this loop or recursion is also considered as <\/span>O(1)<\/span> time complexity. Here is the example- (c-constant) <\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = <\/span>O(1)<\/span><\/span><\/p>\n

2. <\/span>Loop Statements:<\/span><\/span><\/h2>\n

The running time of a loop, can be expressed as the running time of the statements inside the loop (including tests) multiplies by the number of iterations.<\/span><\/span><\/p>\n

Example 1-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = c*n = <\/span>O(n) <\/span><\/span><\/p>\n

or<\/span><\/span><\/p>\n

There is one more definition for this section, i.e., Time complexity of a loop can be considered as <\/span>O(n),<\/span> if the variable used in loop is incremented\/decremented by a constant value.<\/span><\/span><\/p>\n

Example 2-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Here, c – positive integer constant<\/span><\/span><\/p>\n

Hence, Time Complexity = <\/span>O(n)<\/span><\/span><\/p>\n

3. <\/span>Nested Loop Statements:<\/span><\/span><\/h2>\n

If we have to analyze the time complexity of the nested loop statements, then always analyze from the inside out. Total time complexity is the product of the sizes of all the loops.<\/span><\/span><\/p>\n

Example-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = c*n*n = c*n<\/span>2<\/span><\/span> = <\/span>O(n<\/span>2<\/span><\/span>)<\/span><\/span><\/p>\n

4. <\/span>Consecutive Loop Statements:<\/span><\/span><\/h2>\n

In the case of consecutive loop statements, add the time complexities of individual loops.<\/span><\/span><\/p>\n

Example-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = O(m) + O(n) =<\/span> O(m+n) <\/span><\/span><\/p>\n

5. <\/span>Logarithmic Complexity:<\/span><\/span><\/h2>\n

Time complexity of a loop is considered as <\/span>O(logn)<\/span>, if the loop variable is multiplied\/divided by a constant value.<\/span><\/span><\/p>\n

Example 1-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = <\/span>O(log<\/span>c<\/span><\/span>n) <\/span><\/span><\/p>\n

or we can say that, in the above example, the loop runs<\/span> (log<\/span>c<\/span><\/span>n) <\/span>times.<\/span><\/span><\/p>\n

Why here is ‘c’ in the log base? <\/span><\/span><\/p>\n

Let c=2 in the above example,<\/span><\/span><\/p>\n

i : 1, 2, 4, 8,……, n<\/span><\/span><\/p>\n

i : <\/span>2<\/span>0<\/span><\/span>, 2<\/span>1<\/span><\/span>, 2<\/span>2<\/span><\/span>, 2<\/span>3<\/span><\/span>,…., <\/span>2<\/span>k<\/span><\/span>   <\/span><\/span><\/p>\n

Hence, n = 2<\/span>k<\/span><\/span> <\/span><\/span><\/p>\n

Taking logarithm in both sides,<\/span><\/span><\/p>\n

log<\/span>2<\/span><\/span>n = k*log<\/span>2<\/span><\/span>2<\/span><\/span><\/p>\n

k = log<\/span>2<\/span><\/span>n <\/span><\/span><\/p>\n

Hence, T(n) = <\/span>O(log<\/span>2<\/span><\/span>n)<\/span><\/span><\/p>\n

and<\/span><\/span><\/p>\n

Time complexity of a loop is considered as <\/span>O(loglogn)<\/span>,<\/span> <\/span>if the loop variable is reduced\/increased exponentially by a constant value.<\/span><\/span><\/p>\n

Example 2-<\/span><\/span><\/p>\n

<\/span><\/p>\n

Hence, Time Complexity = <\/span>O(log<\/span>c<\/span><\/span>logn)<\/span><\/span><\/p>\n

Why here is ‘c’ in the log base? Try to prove it. Take c=3,4….or some other constant value.<\/span><\/span><\/p>\n

If you find any problem related to this article, please comment below or contact me <\/span>here<\/a><\/span>.<\/span><\/span><\/div>\n

<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Do you Know? In how many ways, you can express your algorithm? There are two ways to express your algorithms- 1. Iterative Algorithms 2. Recursive Algorithms Recursive algorithms can be converted into iterative algorithms and iterative algorithms can be converted into recursive algorithms, both have same in power. We will…<\/p>\n

Read the postGuidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3178","post","type-post","status-publish","format-standard","hentry","category-infinity-fitness","excerpt","zoom","full-without-featured","even","excerpt-0"],"yoast_head":"\nGuidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS | ManOrInfinity<\/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:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS\" \/>\n<meta property=\"og:description\" content=\"Do you Know? In how many ways, you can express your algorithm? There are two ways to express your algorithms- 1. Iterative Algorithms 2. Recursive Algorithms Recursive algorithms can be converted into iterative algorithms and iterative algorithms can be converted into recursive algorithms, both have same in power. We will…\" \/>\n<meta property=\"og:url\" content=\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\" \/>\n<meta property=\"og:site_name\" content=\"ManOrInfinity\" \/>\n<meta property=\"article:published_time\" content=\"2021-06-09T17:08:00+00:00\" \/>\n<meta name=\"author\" content=\"manorinfinity\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@manorinfinity\" \/>\n<meta name=\"twitter:site\" content=\"@manorinfinity\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"manorinfinity\" \/>\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:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\"},\"author\":{\"name\":\"manorinfinity\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"headline\":\"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS\",\"datePublished\":\"2021-06-09T17:08:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\"},\"wordCount\":502,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"articleSection\":[\"Infinity Fitness\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\",\"url\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\",\"name\":\"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS | ManOrInfinity\",\"isPartOf\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\"},\"datePublished\":\"2021-06-09T17:08:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/manorinfinity.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#website\",\"url\":\"https:\/\/manorinfinity.com\/blog\/\",\"name\":\"ManOrInfinity\",\"description\":\"Thrive towards greatness\",\"publisher\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/manorinfinity.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901\",\"name\":\"manorinfinity\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png\",\"contentUrl\":\"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png\",\"width\":282,\"height\":260,\"caption\":\"manorinfinity\"},\"logo\":{\"@id\":\"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/\"},\"description\":\"Complex Problem Solver, Outloud Thinker, An Outstanding Writer, and a very curious human being\",\"sameAs\":[\"http:\/\/manorinfinity.com\"],\"url\":\"https:\/\/manorinfinity.com\/blog\/author\/manorinfinity\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS | ManOrInfinity","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:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/","og_locale":"en_US","og_type":"article","og_title":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS","og_description":"Do you Know? In how many ways, you can express your algorithm? There are two ways to express your algorithms- 1. Iterative Algorithms 2. Recursive Algorithms Recursive algorithms can be converted into iterative algorithms and iterative algorithms can be converted into recursive algorithms, both have same in power. We will…","og_url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/","og_site_name":"ManOrInfinity","article_published_time":"2021-06-09T17:08:00+00:00","author":"manorinfinity","twitter_card":"summary_large_image","twitter_creator":"@manorinfinity","twitter_site":"@manorinfinity","twitter_misc":{"Written by":"manorinfinity","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#article","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/"},"author":{"name":"manorinfinity","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"headline":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS","datePublished":"2021-06-09T17:08:00+00:00","mainEntityOfPage":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/"},"wordCount":502,"commentCount":0,"publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"articleSection":["Infinity Fitness"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/","url":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/","name":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS | ManOrInfinity","isPartOf":{"@id":"https:\/\/manorinfinity.com\/blog\/#website"},"datePublished":"2021-06-09T17:08:00+00:00","breadcrumb":{"@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/manorinfinity.com\/blog\/2021\/06\/09\/guidelines-for-asymptotic-notations-how-to-calculate-time-complexity-bitsofcs\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/manorinfinity.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Guidelines For Asymptotic Notations | How to Calculate Time Complexity | BitsOfCS"}]},{"@type":"WebSite","@id":"https:\/\/manorinfinity.com\/blog\/#website","url":"https:\/\/manorinfinity.com\/blog\/","name":"ManOrInfinity","description":"Thrive towards greatness","publisher":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/manorinfinity.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/1172b1895b5eb7e49cc8640e49255901","name":"manorinfinity","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/","url":"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png","contentUrl":"http:\/\/manorinfinity.com\/wp-content\/uploads\/2023\/06\/moi-logo.png","width":282,"height":260,"caption":"manorinfinity"},"logo":{"@id":"https:\/\/manorinfinity.com\/blog\/#\/schema\/person\/image\/"},"description":"Complex Problem Solver, Outloud Thinker, An Outstanding Writer, and a very curious human being","sameAs":["http:\/\/manorinfinity.com"],"url":"https:\/\/manorinfinity.com\/blog\/author\/manorinfinity\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/comments?post=3178"}],"version-history":[{"count":0,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/posts\/3178\/revisions"}],"wp:attachment":[{"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/media?parent=3178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/categories?post=3178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/manorinfinity.com\/blog\/wp-json\/wp\/v2\/tags?post=3178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}