mirror of
https://github.com/mfocko/blog.git
synced 2024-11-14 01:59:42 +01:00
95 lines
No EOL
57 KiB
HTML
95 lines
No EOL
57 KiB
HTML
<!doctype html>
|
||
<html lang="en" dir="ltr" class="docs-wrapper plugin-docs plugin-id-algorithms docs-version-current docs-doc-page docs-doc-id-time-complexity/extend" data-has-hydrated="false">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="generator" content="Docusaurus v3.0.0">
|
||
<title data-rh="true">Time complexity of ‹extend› | mf</title><meta data-rh="true" name="viewport" content="width=device-width,initial-scale=1"><meta data-rh="true" name="twitter:card" content="summary_large_image"><meta data-rh="true" property="og:url" content="https://blog.mfocko.xyz/algorithms/time-complexity/extend/"><meta data-rh="true" property="og:locale" content="en"><meta data-rh="true" name="docusaurus_locale" content="en"><meta data-rh="true" name="docsearch:language" content="en"><meta data-rh="true" name="docusaurus_version" content="current"><meta data-rh="true" name="docusaurus_tag" content="docs-algorithms-current"><meta data-rh="true" name="docsearch:version" content="current"><meta data-rh="true" name="docsearch:docusaurus_tag" content="docs-algorithms-current"><meta data-rh="true" property="og:title" content="Time complexity of ‹extend› | mf"><meta data-rh="true" name="description" content="How to make inefficient algorithm unknowingly.
|
||
"><meta data-rh="true" property="og:description" content="How to make inefficient algorithm unknowingly.
|
||
"><link data-rh="true" rel="icon" href="/img/favicon.ico"><link data-rh="true" rel="canonical" href="https://blog.mfocko.xyz/algorithms/time-complexity/extend/"><link data-rh="true" rel="alternate" href="https://blog.mfocko.xyz/algorithms/time-complexity/extend/" hreflang="en"><link data-rh="true" rel="alternate" href="https://blog.mfocko.xyz/algorithms/time-complexity/extend/" hreflang="x-default"><link data-rh="true" rel="preconnect" href="https://0VXRFPR4QF-dsn.algolia.net" crossorigin="anonymous"><link rel="search" type="application/opensearchdescription+xml" title="mf" href="/opensearch.xml">
|
||
|
||
|
||
|
||
<link rel="alternate" type="application/rss+xml" href="/blog/rss.xml" title="mf RSS Feed">
|
||
<link rel="alternate" type="application/atom+xml" href="/blog/atom.xml" title="mf Atom Feed">
|
||
<link rel="alternate" type="application/json" href="/blog/feed.json" title="mf JSON Feed">
|
||
|
||
|
||
|
||
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.13.24/dist/katex.min.css" integrity="sha384-odtC+0UGzzFL/6PNoE8rX/SPcQDXBJ+uRepguP4QkPCm2LBxH3FA3y+fKSiJ+AmM" crossorigin="anonymous"><link rel="stylesheet" href="/assets/css/styles.b9f07789.css">
|
||
<script src="/assets/js/runtime~main.2fbb72ea.js" defer="defer"></script>
|
||
<script src="/assets/js/main.0477685f.js" defer="defer"></script>
|
||
</head>
|
||
<body class="navigation-with-keyboard">
|
||
<script>!function(){function t(t){document.documentElement.setAttribute("data-theme",t)}var e=function(){try{return new URLSearchParams(window.location.search).get("docusaurus-theme")}catch(t){}}()||function(){try{return localStorage.getItem("theme")}catch(t){}}();t(null!==e?e:"light")}(),function(){try{const c=new URLSearchParams(window.location.search).entries();for(var[t,e]of c)if(t.startsWith("docusaurus-data-")){var a=t.replace("docusaurus-data-","data-");document.documentElement.setAttribute(a,e)}}catch(t){}}()</script><div id="__docusaurus"><div role="region" aria-label="Skip to main content"><a class="skipToContent_fXgn" href="#__docusaurus_skipToContent_fallback">Skip to main content</a></div><nav aria-label="Main" class="navbar navbar--fixed-top"><div class="navbar__inner"><div class="navbar__items"><button aria-label="Toggle navigation bar" aria-expanded="false" class="navbar__toggle clean-btn" type="button"><svg width="30" height="30" viewBox="0 0 30 30" aria-hidden="true"><path stroke="currentColor" stroke-linecap="round" stroke-miterlimit="10" stroke-width="2" d="M4 7h22M4 15h22M4 23h22"></path></svg></button><a class="navbar__brand" href="/"><b class="navbar__title text--truncate">mf</b></a><div class="navbar__item dropdown dropdown--hoverable"><a href="#" aria-haspopup="true" aria-expanded="false" role="button" class="navbar__link">Additional FI MU materials</a><ul class="dropdown__menu"><li><a aria-current="page" class="dropdown__link dropdown__link--active" href="/algorithms/">Algorithms</a></li><li><a class="dropdown__link" href="/c/">C</a></li><li><a class="dropdown__link" href="/cpp/">C++</a></li></ul></div><a class="navbar__item navbar__link" href="/contributions/">Contributions</a><a class="navbar__item navbar__link" href="/talks/">Talks</a></div><div class="navbar__items navbar__items--right"><a class="navbar__item navbar__link" href="/blog/">Blog</a><div class="toggle_vylO colorModeToggle_DEke"><button class="clean-btn toggleButton_gllP toggleButtonDisabled_aARS" type="button" disabled="" title="Switch between dark and light mode (currently light mode)" aria-label="Switch between dark and light mode (currently light mode)" aria-live="polite"><svg viewBox="0 0 24 24" width="24" height="24" class="lightToggleIcon_pyhR"><path fill="currentColor" d="M12,9c1.65,0,3,1.35,3,3s-1.35,3-3,3s-3-1.35-3-3S10.35,9,12,9 M12,7c-2.76,0-5,2.24-5,5s2.24,5,5,5s5-2.24,5-5 S14.76,7,12,7L12,7z M2,13l2,0c0.55,0,1-0.45,1-1s-0.45-1-1-1l-2,0c-0.55,0-1,0.45-1,1S1.45,13,2,13z M20,13l2,0c0.55,0,1-0.45,1-1 s-0.45-1-1-1l-2,0c-0.55,0-1,0.45-1,1S19.45,13,20,13z M11,2v2c0,0.55,0.45,1,1,1s1-0.45,1-1V2c0-0.55-0.45-1-1-1S11,1.45,11,2z M11,20v2c0,0.55,0.45,1,1,1s1-0.45,1-1v-2c0-0.55-0.45-1-1-1C11.45,19,11,19.45,11,20z M5.99,4.58c-0.39-0.39-1.03-0.39-1.41,0 c-0.39,0.39-0.39,1.03,0,1.41l1.06,1.06c0.39,0.39,1.03,0.39,1.41,0s0.39-1.03,0-1.41L5.99,4.58z M18.36,16.95 c-0.39-0.39-1.03-0.39-1.41,0c-0.39,0.39-0.39,1.03,0,1.41l1.06,1.06c0.39,0.39,1.03,0.39,1.41,0c0.39-0.39,0.39-1.03,0-1.41 L18.36,16.95z M19.42,5.99c0.39-0.39,0.39-1.03,0-1.41c-0.39-0.39-1.03-0.39-1.41,0l-1.06,1.06c-0.39,0.39-0.39,1.03,0,1.41 s1.03,0.39,1.41,0L19.42,5.99z M7.05,18.36c0.39-0.39,0.39-1.03,0-1.41c-0.39-0.39-1.03-0.39-1.41,0l-1.06,1.06 c-0.39,0.39-0.39,1.03,0,1.41s1.03,0.39,1.41,0L7.05,18.36z"></path></svg><svg viewBox="0 0 24 24" width="24" height="24" class="darkToggleIcon_wfgR"><path fill="currentColor" d="M9.37,5.51C9.19,6.15,9.1,6.82,9.1,7.5c0,4.08,3.32,7.4,7.4,7.4c0.68,0,1.35-0.09,1.99-0.27C17.45,17.19,14.93,19,12,19 c-3.86,0-7-3.14-7-7C5,9.07,6.81,6.55,9.37,5.51z M12,3c-4.97,0-9,4.03-9,9s4.03,9,9,9s9-4.03,9-9c0-0.46-0.04-0.92-0.1-1.36 c-0.98,1.37-2.58,2.26-4.4,2.26c-2.98,0-5.4-2.42-5.4-5.4c0-1.81,0.89-3.42,2.26-4.4C12.92,3.04,12.46,3,12,3L12,3z"></path></svg></button></div><div class="navbarSearchContainer_Bca1"><button type="button" class="DocSearch DocSearch-Button" aria-label="Search"><span class="DocSearch-Button-Container"><svg width="20" height="20" class="DocSearch-Search-Icon" viewBox="0 0 20 20"><path d="M14.386 14.386l4.0877 4.0877-4.0877-4.0877c-2.9418 2.9419-7.7115 2.9419-10.6533 0-2.9419-2.9418-2.9419-7.7115 0-10.6533 2.9418-2.9419 7.7115-2.9419 10.6533 0 2.9419 2.9418 2.9419 7.7115 0 10.6533z" stroke="currentColor" fill="none" fill-rule="evenodd" stroke-linecap="round" stroke-linejoin="round"></path></svg><span class="DocSearch-Button-Placeholder">Search</span></span><span class="DocSearch-Button-Keys"></span></button></div></div></div><div role="presentation" class="navbar-sidebar__backdrop"></div></nav><div id="__docusaurus_skipToContent_fallback" class="main-wrapper mainWrapper_z2l0"><div class="docsWrapper_hBAB"><button aria-label="Scroll back to top" class="clean-btn theme-back-to-top-button backToTopButton_sjWU" type="button"></button><div class="docRoot_UBD9"><aside class="theme-doc-sidebar-container docSidebarContainer_YfHR"><div class="sidebarViewport_aRkj"><div class="sidebar_njMd"><nav aria-label="Docs sidebar" class="menu thin-scrollbar menu_SIkG"><ul class="theme-doc-sidebar-menu menu__list"><li class="theme-doc-sidebar-item-link theme-doc-sidebar-item-link-level-1 menu__list-item"><a class="menu__link" href="/algorithms/">Introduction</a></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/algorithms-and-correctness/">Algorithms and Correctness</a><button aria-label="Expand sidebar category 'Algorithms and Correctness'" type="button" class="clean-btn menu__caret"></button></div></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist menu__link--active" aria-expanded="true" href="/algorithms/category/asymptotic-notation-and-time-complexity/">Asymptotic Notation and Time Complexity</a><button aria-label="Collapse sidebar category 'Asymptotic Notation and Time Complexity'" type="button" class="clean-btn menu__caret"></button></div><ul style="display:block;overflow:visible;height:auto" class="menu__list"><li class="theme-doc-sidebar-item-link theme-doc-sidebar-item-link-level-2 menu__list-item"><a class="menu__link menu__link--active" aria-current="page" tabindex="0" href="/algorithms/time-complexity/extend/">Time complexity of ‹extend›</a></li></ul></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/recursion/">Recursion</a><button aria-label="Expand sidebar category 'Recursion'" type="button" class="clean-btn menu__caret"></button></div></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/red-black-trees/">Red-Black Trees</a><button aria-label="Expand sidebar category 'Red-Black Trees'" type="button" class="clean-btn menu__caret"></button></div></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/graphs/">Graphs</a><button aria-label="Expand sidebar category 'Graphs'" type="button" class="clean-btn menu__caret"></button></div></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/paths-in-graphs/">Paths in Graphs</a><button aria-label="Expand sidebar category 'Paths in Graphs'" type="button" class="clean-btn menu__caret"></button></div></li><li class="theme-doc-sidebar-item-category theme-doc-sidebar-item-category-level-1 menu__list-item menu__list-item--collapsed"><div class="menu__list-item-collapsible"><a class="menu__link menu__link--sublist" aria-expanded="false" href="/algorithms/category/hash-tables/">Hash Tables</a><button aria-label="Expand sidebar category 'Hash Tables'" type="button" class="clean-btn menu__caret"></button></div></li></ul></nav><button type="button" title="Collapse sidebar" aria-label="Collapse sidebar" class="button button--secondary button--outline collapseSidebarButton_PEFL"><svg width="20" height="20" aria-hidden="true" class="collapseSidebarButtonIcon_kv0_"><g fill="#7a7a7a"><path d="M9.992 10.023c0 .2-.062.399-.172.547l-4.996 7.492a.982.982 0 01-.828.454H1c-.55 0-1-.453-1-1 0-.2.059-.403.168-.551l4.629-6.942L.168 3.078A.939.939 0 010 2.528c0-.548.45-.997 1-.997h2.996c.352 0 .649.18.828.45L9.82 9.472c.11.148.172.347.172.55zm0 0"></path><path d="M19.98 10.023c0 .2-.058.399-.168.547l-4.996 7.492a.987.987 0 01-.828.454h-3c-.547 0-.996-.453-.996-1 0-.2.059-.403.168-.551l4.625-6.942-4.625-6.945a.939.939 0 01-.168-.55 1 1 0 01.996-.997h3c.348 0 .649.18.828.45l4.996 7.492c.11.148.168.347.168.55zm0 0"></path></g></svg></button></div></div></aside><main class="docMainContainer_TBSr"><div class="container padding-top--md padding-bottom--lg"><div class="row"><div class="col docItemCol_VOVn"><div class="docItemContainer_Djhp"><article><nav class="theme-doc-breadcrumbs breadcrumbsContainer_Z_bl" aria-label="Breadcrumbs"><ul class="breadcrumbs" itemscope="" itemtype="https://schema.org/BreadcrumbList"><li class="breadcrumbs__item"><a aria-label="Home page" class="breadcrumbs__link" href="/"><svg viewBox="0 0 24 24" class="breadcrumbHomeIcon_YNFT"><path d="M10 19v-5h4v5c0 .55.45 1 1 1h3c.55 0 1-.45 1-1v-7h1.7c.46 0 .68-.57.33-.87L12.67 3.6c-.38-.34-.96-.34-1.34 0l-8.36 7.53c-.34.3-.13.87.33.87H5v7c0 .55.45 1 1 1h3c.55 0 1-.45 1-1z" fill="currentColor"></path></svg></a></li><li itemscope="" itemprop="itemListElement" itemtype="https://schema.org/ListItem" class="breadcrumbs__item"><a class="breadcrumbs__link" itemprop="item" href="/algorithms/category/asymptotic-notation-and-time-complexity/"><span itemprop="name">Asymptotic Notation and Time Complexity</span></a><meta itemprop="position" content="1"></li><li itemscope="" itemprop="itemListElement" itemtype="https://schema.org/ListItem" class="breadcrumbs__item breadcrumbs__item--active"><span class="breadcrumbs__link" itemprop="name">Time complexity of ‹extend›</span><meta itemprop="position" content="2"></li></ul></nav><div class="tocCollapsible_ETCw theme-doc-toc-mobile tocMobile_ITEo"><button type="button" class="clean-btn tocCollapsibleButton_TO0P">On this page</button></div><div class="theme-doc-markdown markdown"><header><h1>Time complexity of ‹extend›</h1></header><h2 class="anchor anchorWithStickyNavbar_LWe7" id="introduction">Introduction<a href="#introduction" class="hash-link" aria-label="Direct link to Introduction" title="Direct link to Introduction"></a></h2>
|
||
<p>Each year there is a lot of confusion regarding time complexity of the <code>extend</code> operation on the lists in Python. I will introduce two specific examples from previous year and also will try to explain it on one of the possible implementations of <code>extend</code> operation.</p>
|
||
<h2 class="anchor anchorWithStickyNavbar_LWe7" id="technicalities">Technicalities<a href="#technicalities" class="hash-link" aria-label="Direct link to Technicalities" title="Direct link to Technicalities"></a></h2>
|
||
<p>At the beginning we should clear some of the “myths” regarding extending of the lists. There is a common misunderstanding regarding differences between <code>a += b</code>, <code>a.extend(b)</code> and <code>a + b</code>.</p>
|
||
<ul>
|
||
<li>
|
||
<p><code>a.extend(b)</code> - adds all elements from <code>b</code> to <code>a</code>.</p>
|
||
<p>Time complexity: <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>, where <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em"></span><span class="mord mathnormal">n</span></span></span></span> denotes the length of <code>b</code>.</p>
|
||
</li>
|
||
<li>
|
||
<p><code>a += b</code> - equivalent to <code>a.extend(b)</code></p>
|
||
</li>
|
||
<li>
|
||
<p><code>a + b</code> - constructs a new list that contains elements from <code>a</code> followed by
|
||
elements from <code>b</code>.</p>
|
||
<p>Time complexity: <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(m + n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>, where <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">m, n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.1944em"></span><span class="mord mathnormal">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em"></span><span class="mord mathnormal">n</span></span></span></span> denote the length of
|
||
<code>a</code> and <code>b</code> respectively.</p>
|
||
<p>Space complexity: <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(m + n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2222em"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>, where <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">m, n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.1944em"></span><span class="mord mathnormal">m</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em"></span><span class="mord mathnormal">n</span></span></span></span> denote the length of
|
||
<code>a</code> and <code>b</code> respectively, since we construct new list.</p>
|
||
</li>
|
||
</ul>
|
||
<h2 class="anchor anchorWithStickyNavbar_LWe7" id="example-1">Example #1<a href="#example-1" class="hash-link" aria-label="Direct link to Example #1" title="Direct link to Example #1"></a></h2>
|
||
<p>Let us assume function that uses divide & conquer strategy to return indices at which we can find specific element in any list.</p>
|
||
<div class="language-py codeBlockContainer_Ckt0 theme-code-block" style="--prism-background-color:hsl(230, 1%, 98%);--prism-color:hsl(230, 8%, 24%)"><div class="codeBlockContent_biex"><pre tabindex="0" class="prism-code language-py codeBlock_bY9V thin-scrollbar" style="background-color:hsl(230, 1%, 98%);color:hsl(230, 8%, 24%)"><code class="codeBlockLines_e6Vv codeBlockLinesWithNumbering_o6Pm"><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token keyword" style="color:hsl(301, 63%, 40%)">def</span><span class="token plain"> </span><span class="token function" style="color:hsl(221, 87%, 60%)">recursive_find_in_list</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> List</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token plain">Any</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> key</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> Any</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> lower</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> </span><span class="token builtin" style="color:hsl(119, 34%, 47%)">int</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> upper</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> </span><span class="token builtin" style="color:hsl(119, 34%, 47%)">int</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"></span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">-</span><span class="token operator" style="color:hsl(221, 87%, 60%)">></span><span class="token plain"> List</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token builtin" style="color:hsl(119, 34%, 47%)">int</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">if</span><span class="token plain"> lower </span><span class="token operator" style="color:hsl(221, 87%, 60%)">==</span><span class="token plain"> upper</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">return</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token plain">lower</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">if</span><span class="token plain"> values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token plain">lower</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">==</span><span class="token plain"> key </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">else</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> indices </span><span class="token operator" style="color:hsl(221, 87%, 60%)">=</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> mid </span><span class="token operator" style="color:hsl(221, 87%, 60%)">=</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">lower </span><span class="token operator" style="color:hsl(221, 87%, 60%)">+</span><span class="token plain"> upper</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">//</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">2</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> indices</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">.</span><span class="token plain">extend</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">recursive_find_in_list</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> key</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> lower</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> mid</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> indices</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">.</span><span class="token plain">extend</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">recursive_find_in_list</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> key</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> mid </span><span class="token operator" style="color:hsl(221, 87%, 60%)">+</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">1</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> upper</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">return</span><span class="token plain"> indices</span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"></span><span class="token keyword" style="color:hsl(301, 63%, 40%)">def</span><span class="token plain"> </span><span class="token function" style="color:hsl(221, 87%, 60%)">find_in_list</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> List</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token plain">Any</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> key</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"> Any</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">-</span><span class="token operator" style="color:hsl(221, 87%, 60%)">></span><span class="token plain"> List</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">[</span><span class="token builtin" style="color:hsl(119, 34%, 47%)">int</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">]</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">:</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">return</span><span class="token plain"> recursive_find_in_list</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> key</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">0</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token builtin" style="color:hsl(119, 34%, 47%)">len</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">values</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">-</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">1</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span></span><br></span></code></pre><div class="buttonGroup__atx"><button type="button" aria-label="Copy code to clipboard" title="Copy" class="clean-btn"><span class="copyButtonIcons_eSgA" aria-hidden="true"><svg viewBox="0 0 24 24" class="copyButtonIcon_y97N"><path fill="currentColor" d="M19,21H8V7H19M19,5H8A2,2 0 0,0 6,7V21A2,2 0 0,0 8,23H19A2,2 0 0,0 21,21V7A2,2 0 0,0 19,5M16,1H4A2,2 0 0,0 2,3V17H4V3H16V1Z"></path></svg><svg viewBox="0 0 24 24" class="copyButtonSuccessIcon_LjdS"><path fill="currentColor" d="M21,7L9,19L3.5,13.5L4.91,12.09L9,16.17L19.59,5.59L21,7Z"></path></svg></span></button></div></div></div>
|
||
<p>This implementation works nicely, <code>extend</code> is linear (with the respect to the length of the list that is being appended).</p>
|
||
<p>Let us try to dissect the way this function works on some specific input (that will be pushed to the extreme, <em>just in case</em> ;)</p>
|
||
<p><code>find_in_list([1] * 5000, 1)</code>. What shall be the result of this? Since we have <code>key = 1</code> and the list contains only <code>1</code>s, we should get list of <strong>all</strong> indices.</p>
|
||
<p>If we were to draw a tree of call hierarchy of <code>recursive_find_in_list</code>, we would notice that in sum it is still linear to the length. <strong>However we use <code>extend</code>!</strong></p>
|
||
<p>In the leaves of the tree we return lists of length 1. In this case it means calling <code>extend</code> 5000-times at the second-to-last level of the tree on the 1-element long lists, next level 2500 calls on 2-elements long lists, next one 1250 on 4-elements long lists, etc. At the top-level we get 2 calls on 5000/2-element long lists.</p>
|
||
<p>A lot of <code>extend</code> calls, right? And the lengths of the lists are growing (in this example, second call happens on 2500-elements long lists).</p>
|
||
<p>Because of the <code>extend</code> in each level of the tree (call hierarchy) we traverse all of the elements. That means:</p>
|
||
<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>⋅</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(n \cdot \log n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mop">lo<span style="margin-right:0.01389em">g</span></span><span class="mspace" style="margin-right:0.1667em"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></span>
|
||
<p>because we have <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>log</mi><mo></mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\log n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em"></span><span class="mop">lo<span style="margin-right:0.01389em">g</span></span><span class="mspace" style="margin-right:0.1667em"></span><span class="mord mathnormal">n</span></span></span></span> levels in the tree and <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em"></span><span class="mord mathnormal">n</span></span></span></span> elements at each level.</p>
|
||
<h2 class="anchor anchorWithStickyNavbar_LWe7" id="example-2">Example #2<a href="#example-2" class="hash-link" aria-label="Direct link to Example #2" title="Direct link to Example #2"></a></h2>
|
||
<p>As we could observe in the example above, <code>extend</code> iterates over all of the elements that it adds. In case of recursive calls, it results in iterating over the same elements multiple times.</p>
|
||
<p>Consider constructing of this list:</p>
|
||
<p><img loading="lazy" alt="Rendered construction of the list" src="/assets/images/construction_light-02b0be76041a8b1379107378e8f8b64c.svg#gh-light-mode-only" width="851" height="276" class="img_ev3q">
|
||
<img loading="lazy" alt="Rendered construction of the list" src="/assets/images/construction_dark-fac28e7cafcc43d7e2fb5f0b6c25504e.svg#gh-dark-mode-only" width="851" height="276" class="img_ev3q"></p>
|
||
<p>Let us assume that you extend the result with the list that you get from the recursive call.</p>
|
||
<ul>
|
||
<li>
|
||
<p>B iterates through 1, 2 and 3; returns <code>[1, 2, 3]</code></p>
|
||
</li>
|
||
<li>
|
||
<p>C iterates through 4, 5 and 6; returns <code>[4, 5, 6]</code></p>
|
||
</li>
|
||
<li>
|
||
<p>D iterates through 7, 8 and 9; returns <code>[7, 8, 9]</code></p>
|
||
</li>
|
||
<li>
|
||
<p>now we return those lists to the calls from A), so each of the <code>extend</code> calls iterates through:</p>
|
||
<ul>
|
||
<li>1, 2, 3 that was returned from B</li>
|
||
<li>4, 5, 6 that was returned from C</li>
|
||
<li>7, 8, 9 that was returned from D</li>
|
||
</ul>
|
||
<p>and returns <code>[1, 2, 3, 4, 5, 6, 7, 8, 9]</code></p>
|
||
</li>
|
||
</ul>
|
||
<p>If the recursion had bigger depth and/or more elements, it would iterate through them more than twice, therefore it does not take constant time to do nor some constant multiple of the input, since it traverses all of the elements in each of the levels.</p>
|
||
<h2 class="anchor anchorWithStickyNavbar_LWe7" id="implementation-of-extend">Implementation of <code>extend</code><a href="#implementation-of-extend" class="hash-link" aria-label="Direct link to implementation-of-extend" title="Direct link to implementation-of-extend"> </a></h2>
|
||
<p>There is an example of dynamic array:</p>
|
||
<ul>
|
||
<li><a href="/files/algorithms/time-complexity/extend/dynlist.h" target="_blank" rel="noopener noreferrer">interface (<code>dynlist.h</code>)</a></li>
|
||
<li><a href="/files/algorithms/time-complexity/extend/dynlist.c" target="_blank" rel="noopener noreferrer">implementation (<code>dynlist.c</code>)</a></li>
|
||
</ul>
|
||
<p>For the sake of <em>Algorithms and Data Structures I</em> we consider <code>APPEND</code> operation, i.e. adding the element to the end of the list, to have time complexity <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> (<strong>amortized</strong>; which is out of the scope of IB002).</p>
|
||
<p>If we have a look at the <code>extend</code> implementation in this dynamic array example:</p>
|
||
<div class="language-c codeBlockContainer_Ckt0 theme-code-block" style="--prism-background-color:hsl(230, 1%, 98%);--prism-color:hsl(230, 8%, 24%)"><div class="codeBlockContent_biex"><pre tabindex="0" class="prism-code language-c codeBlock_bY9V thin-scrollbar" style="background-color:hsl(230, 1%, 98%);color:hsl(230, 8%, 24%)"><code class="codeBlockLines_e6Vv codeBlockLinesWithNumbering_o6Pm"><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token keyword" style="color:hsl(301, 63%, 40%)">void</span><span class="token plain"> </span><span class="token function" style="color:hsl(221, 87%, 60%)">dynamic_array_extend</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token keyword" style="color:hsl(301, 63%, 40%)">struct</span><span class="token plain"> </span><span class="token class-name" style="color:hsl(35, 99%, 36%)">dynamic_array_t</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">*</span><span class="token plain">arr</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">struct</span><span class="token plain"> </span><span class="token class-name" style="color:hsl(35, 99%, 36%)">dynamic_array_t</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">*</span><span class="token plain">src</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"></span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">{</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">if</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">arr </span><span class="token operator" style="color:hsl(221, 87%, 60%)">==</span><span class="token plain"> </span><span class="token constant" style="color:hsl(35, 99%, 36%)">NULL</span><span class="token plain"> </span><span class="token operator" style="color:hsl(221, 87%, 60%)">||</span><span class="token plain"> src </span><span class="token operator" style="color:hsl(221, 87%, 60%)">==</span><span class="token plain"> </span><span class="token constant" style="color:hsl(35, 99%, 36%)">NULL</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">{</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">return</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">}</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain" style="display:inline-block"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token keyword" style="color:hsl(301, 63%, 40%)">for</span><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token class-name" style="color:hsl(35, 99%, 36%)">size_t</span><span class="token plain"> i </span><span class="token operator" style="color:hsl(221, 87%, 60%)">=</span><span class="token plain"> </span><span class="token number" style="color:hsl(35, 99%, 36%)">0</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"> i </span><span class="token operator" style="color:hsl(221, 87%, 60%)"><</span><span class="token plain"> src</span><span class="token operator" style="color:hsl(221, 87%, 60%)">-></span><span class="token plain">count</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"> i</span><span class="token operator" style="color:hsl(221, 87%, 60%)">++</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">{</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token function" style="color:hsl(221, 87%, 60%)">dynamic_array_push_back</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">arr</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> </span><span class="token function" style="color:hsl(221, 87%, 60%)">dynamic_array_at</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">(</span><span class="token plain">src</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">,</span><span class="token plain"> i</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">)</span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">;</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"> </span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">}</span><span class="token plain"></span></span><br></span><span class="token-line codeLine_lJS_" style="color:hsl(230, 8%, 24%)"><span class="codeLineNumber_Tfdd"></span><span class="codeLineContent_feaV"><span class="token plain"></span><span class="token punctuation" style="color:hsl(119, 34%, 47%)">}</span></span><br></span></code></pre><div class="buttonGroup__atx"><button type="button" aria-label="Copy code to clipboard" title="Copy" class="clean-btn"><span class="copyButtonIcons_eSgA" aria-hidden="true"><svg viewBox="0 0 24 24" class="copyButtonIcon_y97N"><path fill="currentColor" d="M19,21H8V7H19M19,5H8A2,2 0 0,0 6,7V21A2,2 0 0,0 8,23H19A2,2 0 0,0 21,21V7A2,2 0 0,0 19,5M16,1H4A2,2 0 0,0 2,3V17H4V3H16V1Z"></path></svg><svg viewBox="0 0 24 24" class="copyButtonSuccessIcon_LjdS"><path fill="currentColor" d="M21,7L9,19L3.5,13.5L4.91,12.09L9,16.17L19.59,5.59L21,7Z"></path></svg></span></button></div></div></div>
|
||
<p>Apart from checking edge cases, we can notice that we run <code>for</code>-loop over the elements from the other array and add them one-by-one to the <code>arr</code>. Time complexity of this operation is time dependant on the <code>src</code> array.</p>
|
||
<p>In this specific implementation, you could also resize the memory allocated for the array in one go and copy <em>whole</em> <code>src</code> array in one go. However even if you did so, it would be still dependant on the size of the <code>src</code> array. Cause you still need to copy <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext mathvariant="monospace">count</mtext><mo stretchy="false">(</mo><mi>s</mi><mi>r</mi><mi>c</mi><mo stretchy="false">)</mo><mo>⋅</mo><mtext mathvariant="monospace">elementSize</mtext><mo stretchy="false">(</mo><mi>s</mi><mi>r</mi><mi>c</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\texttt{count}(src) \cdot \texttt{elementSize}(src)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord text"><span class="mord texttt">count</span></span><span class="mopen">(</span><span class="mord mathnormal">src</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord text"><span class="mord texttt">elementSize</span></span><span class="mopen">(</span><span class="mord mathnormal">src</span><span class="mclose">)</span></span></span></span> bytes. From that we can assume that for specific instance of array the <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext mathvariant="monospace">elementSize</mtext><mo stretchy="false">(</mo><mi>s</mi><mi>r</mi><mi>c</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\texttt{elementSize}(src)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord text"><span class="mord texttt">elementSize</span></span><span class="mopen">(</span><span class="mord mathnormal">src</span><span class="mclose">)</span></span></span></span> is fixed, therefore we consider it a constant. That way we are getting <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mtext mathvariant="monospace">count</mtext><mo stretchy="false">(</mo><mi>s</mi><mi>r</mi><mi>c</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\mathcal{O}(\texttt{count}(src))</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em"></span><span class="mord mathcal" style="margin-right:0.02778em">O</span><span class="mopen">(</span><span class="mord text"><span class="mord texttt">count</span></span><span class="mopen">(</span><span class="mord mathnormal">src</span><span class="mclose">))</span></span></span></span> as a time complexity of our <code>extend</code> operation.</p></div><footer class="theme-doc-footer docusaurus-mt-lg"><div class="theme-doc-footer-tags-row row margin-bottom--sm"><div class="col"><b>Tags:</b><ul class="tags_jXut padding--none margin-left--sm"><li class="tag_QGVx"><a class="tag_zVej tagRegular_sFm0" href="/algorithms/tags/c/">c</a></li><li class="tag_QGVx"><a class="tag_zVej tagRegular_sFm0" href="/algorithms/tags/python/">python</a></li><li class="tag_QGVx"><a class="tag_zVej tagRegular_sFm0" href="/algorithms/tags/dynamic-array/">dynamic array</a></li><li class="tag_QGVx"><a class="tag_zVej tagRegular_sFm0" href="/algorithms/tags/time-complexity/">time complexity</a></li><li class="tag_QGVx"><a class="tag_zVej tagRegular_sFm0" href="/algorithms/tags/recursion/">recursion</a></li></ul></div></div><div class="theme-doc-footer-edit-meta-row row"><div class="col"><a href="https://github.com/mfocko/blog/tree/main/algorithms/03-time-complexity/2021-03-31-extend.md" target="_blank" rel="noopener noreferrer" class="theme-edit-this-page"><svg fill="currentColor" height="20" width="20" viewBox="0 0 40 40" class="iconEdit_Z9Sw" aria-hidden="true"><g><path d="m34.5 11.7l-3 3.1-6.3-6.3 3.1-3q0.5-0.5 1.2-0.5t1.1 0.5l3.9 3.9q0.5 0.4 0.5 1.1t-0.5 1.2z m-29.5 17.1l18.4-18.5 6.3 6.3-18.4 18.4h-6.3v-6.2z"></path></g></svg>Edit this page</a></div><div class="col lastUpdated_vwxv"><span class="theme-last-updated">Last updated<!-- --> on <b><time datetime="2021-03-31T00:00:00.000Z">Mar 31, 2021</time></b></span></div></div></footer></article><nav class="pagination-nav docusaurus-mt-lg" aria-label="Docs pages"><a class="pagination-nav__link pagination-nav__link--prev" href="/algorithms/category/asymptotic-notation-and-time-complexity/"><div class="pagination-nav__sublabel">Previous</div><div class="pagination-nav__label">Asymptotic Notation and Time Complexity</div></a><a class="pagination-nav__link pagination-nav__link--next" href="/algorithms/category/recursion/"><div class="pagination-nav__sublabel">Next</div><div class="pagination-nav__label">Recursion</div></a></nav></div></div><div class="col col--3"><div class="tableOfContents_bqdL thin-scrollbar theme-doc-toc-desktop"><ul class="table-of-contents table-of-contents__left-border"><li><a href="#introduction" class="table-of-contents__link toc-highlight">Introduction</a></li><li><a href="#technicalities" class="table-of-contents__link toc-highlight">Technicalities</a></li><li><a href="#example-1" class="table-of-contents__link toc-highlight">Example #1</a></li><li><a href="#example-2" class="table-of-contents__link toc-highlight">Example #2</a></li><li><a href="#implementation-of-extend" class="table-of-contents__link toc-highlight">Implementation of <code>extend</code></a></li></ul></div></div></div></div></main></div></div></div><footer class="footer footer--dark"><div class="container container-fluid"><div class="row footer__links"><div class="col footer__col"><div class="footer__title">Git</div><ul class="footer__items clean-list"><li class="footer__item"><a href="https://github.com/mfocko" target="_blank" rel="noopener noreferrer" class="footer__link-item">GitHub<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://gitlab.com/mfocko" target="_blank" rel="noopener noreferrer" class="footer__link-item">GitLab<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://git.mfocko.xyz/mfocko" target="_blank" rel="noopener noreferrer" class="footer__link-item">Gitea (self-hosted)<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li></ul></div><div class="col footer__col"><div class="footer__title">Social #1</div><ul class="footer__items clean-list"><li class="footer__item"><a href="https://www.linkedin.com/in/mfocko/" target="_blank" rel="noopener noreferrer" class="footer__link-item">LinkedIn<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://fosstodon.org/@m4tt_314" target="_blank" rel="noopener noreferrer" class="footer__link-item">Fosstodon<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://hachyderm.io/@m4tt_314" target="_blank" rel="noopener noreferrer" class="footer__link-item">Hachyderm.io<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li></ul></div><div class="col footer__col"><div class="footer__title">Social #2</div><ul class="footer__items clean-list"><li class="footer__item"><a href="https://twitter.com/m4tt_314" target="_blank" rel="noopener noreferrer" class="footer__link-item">Twitter<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://twitch.tv/m4tt_314" target="_blank" rel="noopener noreferrer" class="footer__link-item">Twitch<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li><li class="footer__item"><a href="https://ko-fi.com/m4tt_314" target="_blank" rel="noopener noreferrer" class="footer__link-item">Ko-fi<svg width="13.5" height="13.5" aria-hidden="true" viewBox="0 0 24 24" class="iconExternalLink_nPIU"><path fill="currentColor" d="M21 13v10h-21v-19h12v2h-10v15h17v-8h2zm3-12h-10.988l4.035 4-6.977 7.07 2.828 2.828 6.977-7.07 4.125 4.172v-11z"></path></svg></a></li></ul></div></div><div class="footer__bottom text--center"><div class="footer__copyright">Copyright © 2024 Matej Focko.</div></div></div></footer></div>
|
||
</body>
|
||
</html> |