{"id":6868,"date":"2025-06-17T19:17:59","date_gmt":"2025-06-17T13:47:59","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=6868"},"modified":"2025-09-30T12:17:05","modified_gmt":"2025-09-30T06:47:05","slug":"time-space-complexity","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/time-space-complexity\/","title":{"rendered":"Time\/Space Complexity"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\"\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n  --content-max-width: 940px;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: var(--content-max-width);\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  padding: 1rem;\n  box-sizing: border-box;\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n\/* Make <pre> stable and responsive to avoid distortion *\/\n.wp_blog_code-tab-content pre,\n.wp_blog_explanation pre {\n  margin: 0;\n  padding: 1rem 1.25rem;\n  font-size: 0.95rem;\n  overflow-x: auto;            \/* horizontal scroll when needed *\/\n  white-space: pre;            \/* preserve formatting *\/\n  word-break: normal;          \/* don't break words inside code *\/\n  background: var(--code-bg) !important;\n  color: var(--code-text) !important;\n  border-radius: calc(var(--tab-radius) - 2px);\n  box-sizing: border-box;\n  font-family: ui-monospace, SFMono-Regular, Menlo, Monaco, \"Roboto Mono\", \"Courier New\", monospace !important;\n  line-height: 1.45;\n  max-width: 100%;\n}\n\n\/* ensure inline code inside pre is not causing wrapping issues *\/\n.wp_blog_code-tab-content pre code,\n.wp_blog_explanation pre code {\n  background: transparent !important;\n  color: inherit !important;\n  padding: 0 !important;\n}\n\n\/* make sure Prism's long tokens don't overflow the wrapper *\/\n.wp_blog_code-tab-content pre code .token,\n.wp_blog_explanation pre code .token {\n  word-break: normal;\n  white-space: pre;\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n\/* Positioning for toggle *\/\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n\n\/* \u2705 Fix: Make Linear & Binary Search cards visible in dark mode *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation > div > div {\n  background: #1e1e1e !important;\n  color: var(--text-dark);\n  box-shadow: 0 6px 18px rgba(0,0,0,0.5);\n}\n.wp_blog_theme.dark-mode .wp_blog_explanation > div > div h3,\n.wp_blog_theme.dark-mode .wp_blog_explanation > div > div li,\n.wp_blog_theme.dark-mode .wp_blog_explanation > div > div strong,\n.wp_blog_theme.dark-mode .wp_blog_explanation > div > div p {\n  color: var(--text-dark);\n}\n\n\/* Small-screen tweaks so code blocks don't overflow the whole viewport *\/\n@media (max-width: 520px) {\n  .wp_blog_explanation,\n  .wp_blog_code-tabs-container {\n    padding: 1rem;\n  }\n  .wp_blog_main-heading {\n    font-size: 1.6rem;\n    margin-top: 1.25rem;\n  }\n  .wp_blog_code-tab-content pre,\n  .wp_blog_explanation pre {\n    font-size: 0.9rem;\n    padding: 0.75rem;\n  }\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>What is Time Complexity?<\/h2>\n    <p>Time complexity measures how efficient an algorithm is as the input size increases. It's not the same as the actual time taken to run a program.<\/p>\n    <p><code>Time Complexity != Execution Time<\/code><\/p>\n\n    <h2>Linear vs Binary Search<\/h2>\n\n    <div style=\"display: flex; gap: 2rem; flex-wrap: wrap; margin-top: 1.5rem;\">\n      <div style=\"flex: 1 1 420px; background: #fff8ec; padding: 1rem 1.5rem; border-radius: 12px; box-shadow: 0 2px 10px rgba(0,0,0,0.06);\">\n        <h3 style=\"color: #d35400; margin-bottom: 0.75rem;\">Linear Search<\/h3>\n        <ul>\n          <li><strong>Best Case:<\/strong> Element at 1st index \u2192 1 operation<\/li>\n          <li><strong>Average Case:<\/strong> Element at n\/2 index \u2192 n\/2 operations<\/li>\n          <li><strong>Worst Case:<\/strong> Element not found \u2192 n operations<\/li>\n          <li><strong>Time Complexity:<\/strong> O(n)<\/li>\n          <li><strong>Requirement:<\/strong> Can work on unsorted arrays<\/li>\n        <\/ul>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/06\/Screenshot-2025-06-17-at-3.50.59%E2%80%AFPM.png\" alt=\"Linear Search Graph\">\n      <\/div>\n      <div style=\"flex: 1 1 420px; background: #ecfaff; padding: 1rem 1.5rem; border-radius: 12px; box-shadow: 0 2px 10px rgba(0,0,0,0.06);\">\n        <h3 style=\"color: #2980b9; margin-bottom: 0.75rem;\">Binary Search<\/h3>\n        <ul>\n          <li><strong>Best Case:<\/strong> Middle element matched \u2192 1 operation<\/li>\n          <li><strong>Average Case:<\/strong> log\u2082(n) operations<\/li>\n          <li><strong>Worst Case:<\/strong> log\u2082(n) operations<\/li>\n          <li><strong>Time Complexity:<\/strong> O(log n)<\/li>\n          <li><strong>Requirement:<\/strong> Only works on sorted arrays<\/li>\n        <\/ul>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/06\/Screenshot-2025-06-17-at-3.51.05%E2%80%AFPM.png\" alt=\"Binary Search Graph\">\n      <\/div>\n    <\/div>\n\n    <p>\n      When we use <code>Linear Search<\/code> for an input size of 100, it runs 100 times, whereas <code>Binary Search<\/code> takes only 7 steps. This shows that Binary Search is more efficient.\n      As the input size (n) increases, the way an algorithm behaves helps us understand how efficient it is.\n      Also, the graph helps us understand that Binary Search is more efficient.\n    <\/p>\n\n    <h2>Big O Notation<\/h2>\n    <p>It is nothing; just a symbol used to represent the worst-case complexity.<\/p>\n\n    <h2>Code Examples of Time Complexity<\/h2>\n\n    <p><code>O(1)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\n\/\/ Accessing 5th index element\nint value = arr[5];\n    <\/code><\/pre>\n    <p>The time complexity is O(1) because we directly access the 5th index without any iteration.<\/p>\n\n    <p><code>O(n)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\nfor(int i = 0; i < n; i++) {\n    \/\/ do something\n}\n    <\/code><\/pre>\n\n    <p><code>O(log n)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\n\/\/ e.g., Binary Search\nint binarySearch(int arr[], int n, int key) {\n    int low = 0, high = n - 1;\n    while(low <= high) {\n        int mid = (low + high) \/ 2;\n        if(arr[mid] == key) return mid;\n        else if(arr[mid] < key) low = mid + 1;\n        else high = mid - 1;\n    }\n    return -1;\n}\n    <\/code><\/pre>\n\n    <p><code>O(n^2)<\/code> \u2013 Nested Loop<\/p>\n    <pre><code class=\"language-cpp\">\nfor(int i = 0; i < n; i++) {\n    for(int j = 0; j < n; j++) {\n        \/\/ do something\n    }\n}\n    <\/code><\/pre>\n\n    <p><code>O(n log n)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\nfor(int i = 0; i < n; i++) {\n    int temp = n;\n    while(temp > 1) {\n        temp = temp \/ 2;\n        \/\/ do something\n    }\n}\n    <\/code><\/pre>\n\n    <p><code>O(n^3)<\/code> \u2013 Triple Nested Loops<\/p>\n    <pre><code class=\"language-cpp\">\nfor(int i = 0; i < n; i++) {\n    for(int j = 0; j < n; j++) {\n        for(int k = 0; k < n; k++) {\n            \/\/ do something\n        }\n    }\n}\n    <\/code><\/pre>\n\n    <p><code>O(2^n)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\n\/\/ Recursive Fibonacci\nint fib(int n) {\n    if(n <= 1) return n;\n    return fib(n-1) + fib(n-2);\n}\n    <\/code><\/pre>\n\n    <p><code>O(n!)<\/code><\/p>\n    <pre><code class=\"language-cpp\">\n\/\/ Permutation generator\nvoid permute(string s, int l, int r) {\n    if(l == r) {\n        cout << s << endl;\n    } else {\n        for(int i = l; i <= r; i++) {\n            swap(s[l], s[i]);\n            permute(s, l + 1, r);\n            swap(s[l], s[i]); \/\/ backtrack\n        }\n    }\n}\n    <\/code><\/pre>\n\n    <h2>Time Complexity Priorities<\/h2>\n    <ul>\n      <li><code>O(1)<\/code> \u2013 Constant time<\/li>\n      <li><code>O(log n)<\/code> \u2013 e.g., Binary Search<\/li>\n      <li><code>O(n)<\/code> \u2013 e.g., Linear Search<\/li>\n      <li><code>O(n log n)<\/code> \u2013 e.g., Merge Sort<\/li>\n      <li><code>O(n^2)<\/code> \u2013 e.g., Nested Loops<\/li>\n      <li><code>O(n^3)<\/code> \u2013 e.g., Triple Nested Loops<\/li>\n      <li><code>O(2^n)<\/code> \u2013 Recursion (e.g., Fibonacci)<\/li>\n      <li><code>O(n!)<\/code> \u2013 e.g., Brute-force permutations<\/li>\n    <\/ul>\n\n   <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-25-at-10.31.42\u202fAM.png\" alt=\"\">\n\n    <h2>What is Space Complexity?<\/h2>\n    <p>Space complexity refers to how much extra memory an algorithm uses.<\/p>\n\n    <h3>Examples:<\/h3>\n    <ul>\n      <li>Access 5th element: <code>O(1)<\/code><\/li>\n      <li>Find max with variable: <code>O(1)<\/code><\/li>\n      <li>New array: <code>O(n)<\/code><\/li>\n      <li>2D Matrix: <code>O(n^2)<\/code><\/li>\n    <\/ul>\n  <\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 What is Time Complexity? Time complexity measures how efficient an algorithm is as the input size increases. It&#8217;s not the same as the actual time taken to run a program. Time Complexity != Execution Time Linear vs Binary Search Linear Search Best Case: Element at 1st index \u2192 1 operation Average Case: Element at<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[322,260,176,175,811,810,217,314,174,172,311,303],"tags":[],"class_list":["post-6868","post","type-post","status-publish","format-standard","category-algorithms-and-data-structures","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures-and-algorithms","category-dsa","category-interview-experience","category-interview-preparation","category-java","category-javascript","category-namastedev-community","category-tech-tips"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6868","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=6868"}],"version-history":[{"count":14,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6868\/revisions"}],"predecessor-version":[{"id":10168,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6868\/revisions\/10168"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=6868"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=6868"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=6868"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}