<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Jahnavipolasa on Medium]]></title>
        <description><![CDATA[Stories by Jahnavipolasa on Medium]]></description>
        <link>https://medium.com/@jahnavipolasa?source=rss-1f88a4d54505------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*joAAfopJVD7fw6pU</url>
            <title>Stories by Jahnavipolasa on Medium</title>
            <link>https://medium.com/@jahnavipolasa?source=rss-1f88a4d54505------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 04:30:57 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jahnavipolasa/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Time and Space Complexity]]></title>
            <link>https://medium.com/@jahnavipolasa/time-and-space-complexity-8a6b080464be?source=rss-1f88a4d54505------2</link>
            <guid isPermaLink="false">https://medium.com/p/8a6b080464be</guid>
            <category><![CDATA[time-complexity]]></category>
            <category><![CDATA[space-complexity]]></category>
            <category><![CDATA[sad]]></category>
            <category><![CDATA[best-practices]]></category>
            <category><![CDATA[big-o-notation]]></category>
            <dc:creator><![CDATA[Jahnavipolasa]]></dc:creator>
            <pubDate>Sun, 31 May 2026 12:13:22 GMT</pubDate>
            <atom:updated>2026-05-31T12:13:55.535Z</atom:updated>
            <content:encoded><![CDATA[<h3>Time Complexity and Space Complexity: The Two Pillars of Algorithm Analysis</h3><p>When you write code that works, you’ve solved half the problem. The other half is writing code that <em>scales</em> — code that doesn’t collapse under real-world data. That’s where time and space complexity come in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aiWIi2aVs7h9G_oM4Pj2UA.png" /><figcaption>Time and space complexity</figcaption></figure><h3>What Is Complexity Analysis?</h3><p>Complexity analysis is how we measure the <em>efficiency</em> of an algorithm — not in seconds or megabytes (those depend on hardware), but in abstract terms that hold true regardless of what machine you run on.</p><p>We express complexity using <strong>Big O notation</strong>, which describes how an algorithm’s resource usage grows as the input size n increases. The “resource” in question is either time (operations) or memory (space).</p><h3>Time Complexity</h3><p>Time complexity measures <strong>how the number of operations grows</strong> with input size.</p><p>It answers: <em>if I double my input, does my algorithm take twice as long? Four times as long? The same time?</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/745/1*tcC9J7lblKpkIcKzd63EdQ.png" /></figure><h3>Common time complexities, from best to worst:</h3><p><strong>O(1) — Constant time</strong> The algorithm always takes the same number of steps, no matter the input size.</p><pre>def get_first(arr):<br>    return arr[0]   # always one operation</pre><p>Examples: array index access, hash map lookup, stack push/pop.</p><p><strong>O(log n) — Logarithmic time</strong> The algorithm cuts the problem in half each step. Doubling the input adds just <em>one</em> more step.</p><pre>def binary_search(arr, target):<br>    lo, hi = 0, len(arr) - 1<br>    while lo &lt;= hi:<br>        mid = (lo + hi) // 2<br>        if arr[mid] == target: return mid<br>        elif arr[mid] &lt; target: lo = mid + 1<br>        else: hi = mid - 1<br>    return -1</pre><p>Examples: binary search, balanced BST operations. For n = 1,000,000,000 you need only ~30 steps.</p><p><strong>O(n) — Linear time</strong> One operation per element. Input doubles → time doubles.</p><pre>def find_max(arr):<br>    max_val = arr[0]<br>    for x in arr:         # visits every element once<br>        if x &gt; max_val:<br>            max_val = x<br>    return max_val</pre><p>Examples: linear search, single loop, reading a file.</p><p><strong>O(n log n) — Linearithmic time</strong> The sweet spot for sorting. You can’t sort by comparison faster than this (proven mathematically).</p><pre>def merge_sort(arr):<br>    if len(arr) &lt;= 1: return arr<br>    mid = len(arr) // 2<br>    left  = merge_sort(arr[:mid])   # log n levels of splitting<br>    right = merge_sort(arr[mid:])<br>    return merge(left, right)       # O(n) merge per level</pre><p>Examples: merge sort, heap sort, most efficient sorting algorithms.</p><p><strong>O(n²) — Quadratic time</strong> Nested loops over the same input. Double the input → four times the work.</p><pre>def bubble_sort(arr):<br>    for i in range(len(arr)):<br>        for j in range(len(arr) - 1):   # nested loop = n²<br>            if arr[j] &gt; arr[j+1]:<br>                arr[j], arr[j+1] = arr[j+1], arr[j]</pre><p>Examples: bubble sort, selection sort, naive duplicate detection. Tolerable for small inputs (n &lt; 1000), painful beyond that.</p><p><strong>O(2ⁿ) — Exponential time</strong> Every additional element doubles the work. Grows astronomically fast.</p><pre>def fib(n):<br>    if n &lt;= 1: return n<br>    return fib(n-1) + fib(n-2)   # two calls per call → 2ⁿ total</pre><p>For n = 50, this makes over 1 <em>quadrillion</em> calls. Avoid unless the problem forces it (and then use memoization).</p><p><strong>O(n!) — Factorial time</strong> Generates all permutations. n = 20 already produces 2.4 quadrillion operations. Practically only usable for n &lt; 12 or so.</p><p><a href="https://www.bigocheatsheet.com/">Know Thy Complexities!</a></p><h3>Space Complexity</h3><p>Space complexity measures <strong>how much extra memory an algorithm allocates</strong> as input size grows.</p><p>The key word is <em>extra</em> — we measure <em>auxiliary space</em>, meaning memory your algorithm creates beyond the input that was already there. The input itself isn’t charged to you.</p><h3>The same complexities apply, but now for memory:</h3><p><strong>O(1) — Constant space</strong> The algorithm uses a fixed number of variables regardless of input size.</p><pre>def sum_array(arr):<br>    total = 0          # one variable<br>    for x in arr:<br>        total += x<br>    return total<br># Space: O(1) — only &#39;total&#39; is allocated, no matter how big arr is</pre><p><strong>O(n) — Linear space</strong> Memory grows in proportion to input size.</p><pre>def make_copy(arr):<br>    return arr[:]      # allocates a new array of size n<br># Space: O(n)</pre><p>Also applies to recursion depth — a function that recurses n times deep holds n stack frames in memory simultaneously.</p><p><strong>O(n²) — Quadratic space</strong></p><pre>def build_matrix(n):<br>    return [[0] * n for _ in range(n)]<br># Space: O(n²) — n rows × n columns = n² cells</pre><h3>The sneaky space cost: recursion</h3><p>Recursive functions use the <strong>call stack</strong> as memory. Every time a function calls itself, a new frame is pushed onto the stack. This is invisible but real.</p><pre>def countdown(n):      # looks like it uses no space<br>    if n == 0: return<br>    countdown(n - 1)   # but holds n frames in memory at peak!</pre><pre># Space: O(n) — not O(1)!</pre><p>This is one of the most common interview mistakes. An iterative loop uses O(1) space; a recursive equivalent often uses O(n) space.</p><h3>Time vs Space: The Trade-off</h3><p>Here’s the truth at the heart of algorithm design: <strong>you can almost always trade one for the other.</strong></p><p>More memory → less time. Less memory → more time.</p><p>The classic example is the hash map:</p><pre># Naive: find if array has duplicates<br># Time: O(n²)   Space: O(1)<br>def has_duplicate_slow(arr):<br>    for i in range(len(arr)):<br>        for j in range(i+1, len(arr)):<br>            if arr[i] == arr[j]: return True<br>    return False</pre><pre># Smart: use a hash set<br># Time: O(n)    Space: O(n)<br>def has_duplicate_fast(arr):<br>    seen = set()          # extra O(n) memory<br>    for x in arr:<br>        if x in seen: return True<br>        seen.add(x)<br>    return False</pre><p>We paid O(n) space to drop from O(n²) time to O(n) time. For large inputs, that trade is almost always worth it.</p><h3>When to prioritize which:</h3><p>Situation Prioritize Real-time systems, tight deadlines Time Embedded systems, low RAM devices Space Most backend APIs Time (memory is cheap) Mobile apps Space (RAM is limited) Big data pipelines Both — use streaming</p><h3>Analyzing Both Together</h3><p>When you see a piece of code, get into the habit of asking <em>two separate questions</em>:</p><ol><li>How many <strong>operations</strong> execute as n grows? → Time complexity</li><li>How much <strong>memory</strong> is held at peak as n grows? → Space complexity</li></ol><p>They are independent dimensions. Here’s a quick reference:</p><p>Algorithm Time Space Binary search (iterative) O(log n) O(1) Binary search (recursive) O(log n) O(log n) Merge sort O(n log n) O(n) Quick sort (average) O(n log n) O(log n) Hash map lookup O(1) O(n) DFS on a graph O(V + E) O(V) Building a matrix O(n²) O(n²)</p><p>Notice binary search: the iterative version is O(1) space, the recursive version is O(log n) space — same time complexity, different space. That’s a real, meaningful difference.</p><h3>The Golden Rule</h3><blockquote><em>An algorithm is only as good as its worst-case behavior on the inputs you’ll actually see in production.</em></blockquote><p>O(n²) might feel fine on 100 rows in development. Ship it to a database with 500,000 rows and it grinds to a halt. Complexity analysis is how you catch that <em>before</em> it happens — on a whiteboard, not in a post-mortem.</p><p>Master time and space complexity and you’ll never write naively slow code again. Every data structure you learn from here — arrays, hash maps, trees, graphs — comes with a complexity profile. Knowing those profiles is what separates someone who can <em>code</em> from someone who can <em>engineer</em>.</p><h3>Practice</h3><p>To strengthen your understanding of time and space complexity, practice the questions provided in the link below.</p><p><a href="https://jahnavipolasa.github.io/time-space-complexity/time-space-complexity.html">https://jahnavipolasa.github.io/time-space-complexity/time-space-complexity.html</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8a6b080464be" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>