CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Algorithmic efficiency - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"6c3655a2-a63d-486d-bcd2-bc8b366bb069","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Algorithmic_efficiency","wgTitle":"Algorithmic efficiency","wgCurRevisionId":1272259821,"wgRevisionId":1272259821,"wgArticleId":145128,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles needing additional references from January 2024","All articles needing additional references","Wikipedia articles with style issues from January 2024","All articles with style issues","Articles with short description","Short description is different from Wikidata","Use dmy dates from February 2023","Articles containing potentially dated statements from 2018","All articles containing potentially dated statements","All articles with unsourced statements", "Articles with unsourced statements from July 2024","Analysis of algorithms","Computer performance","Software optimization","Software quality"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Algorithmic_efficiency","wgRelevantArticleId":145128,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false, "wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1296251","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=[ "ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Algorithmic efficiency - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Algorithmic_efficiency"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Algorithmic_efficiency&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Algorithmic_efficiency"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Algorithmic_efficiency rootpage-Algorithmic_efficiency skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Algorithmic+efficiency" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Algorithmic+efficiency" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Algorithmic+efficiency" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Algorithmic+efficiency" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Background" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Background"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Background</span> </div> </a> <ul id="toc-Background-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Overview</span> </div> </a> <button aria-controls="toc-Overview-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Overview subsection</span> </button> <ul id="toc-Overview-sublist" class="vector-toc-list"> <li id="toc-Theoretical_analysis" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Theoretical_analysis"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Theoretical analysis</span> </div> </a> <ul id="toc-Theoretical_analysis-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Measuring_performance" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Measuring_performance"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Measuring performance</span> </div> </a> <ul id="toc-Measuring_performance-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation_concerns" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Implementation_concerns"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Implementation concerns</span> </div> </a> <ul id="toc-Implementation_concerns-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Measures_of_resource_usage" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Measures_of_resource_usage"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Measures of resource usage</span> </div> </a> <button aria-controls="toc-Measures_of_resource_usage-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Measures of resource usage subsection</span> </button> <ul id="toc-Measures_of_resource_usage-sublist" class="vector-toc-list"> <li id="toc-Time" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Time"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Time</span> </div> </a> <ul id="toc-Time-sublist" class="vector-toc-list"> <li id="toc-Theory" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Theory"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1.1</span> <span>Theory</span> </div> </a> <ul id="toc-Theory-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Practice" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Practice"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1.2</span> <span>Practice</span> </div> </a> <ul id="toc-Practice-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Space" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Space"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Space</span> </div> </a> <ul id="toc-Space-sublist" class="vector-toc-list"> <li id="toc-Caching_and_memory_hierarchy" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Caching_and_memory_hierarchy"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2.1</span> <span>Caching and memory hierarchy</span> </div> </a> <ul id="toc-Caching_and_memory_hierarchy-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Algorithmic efficiency</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 17 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-17" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">17 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%83%D9%81%D8%A7%D8%A1%D8%A9_%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9" title="كفاءة خوارزمية – Arabic" lang="ar" hreflang="ar" data-title="كفاءة خوارزمية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Alqoritmik_s%C9%99m%C9%99r%C9%99lilik" title="Alqoritmik səmərəlilik – Azerbaijani" lang="az" hreflang="az" data-title="Alqoritmik səmərəlilik" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Efic%C3%A0cia_algor%C3%ADsmica" title="Eficàcia algorísmica – Catalan" lang="ca" hreflang="ca" data-title="Eficàcia algorísmica" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Efektivnost_algoritmu" title="Efektivnost algoritmu – Czech" lang="cs" hreflang="cs" data-title="Efektivnost algoritmu" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Effizienz_(Informatik)" title="Effizienz (Informatik) – German" lang="de" hreflang="de" data-title="Effizienz (Informatik)" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Eficiencia_algor%C3%ADtmica" title="Eficiencia algorítmica – Spanish" lang="es" hreflang="es" data-title="Eficiencia algorítmica" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%DA%A9%D8%A7%D8%B1%D8%A2%DB%8C%DB%8C_%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%DB%8C" title="کارآیی الگوریتمی – Persian" lang="fa" hreflang="fa" data-title="کارآیی الگوریتمی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%99%D7%A2%D7%99%D7%9C%D7%95%D7%AA_%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9E%D7%99%D7%AA" title="יעילות אלגוריתמית – Hebrew" lang="he" hreflang="he" data-title="יעילות אלגוריתמית" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Algoritmisk_effisiens" title="Algoritmisk effisiens – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Algoritmisk effisiens" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Wydajno%C5%9B%C4%87_oprogramowania" title="Wydajność oprogramowania – Polish" lang="pl" hreflang="pl" data-title="Wydajność oprogramowania" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Eficien%C8%9Ba_algoritmilor" title="Eficiența algoritmilor – Romanian" lang="ro" hreflang="ro" data-title="Eficiența algoritmilor" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0" title="Эффективность алгоритма – Russian" lang="ru" hreflang="ru" data-title="Эффективность алгоритма" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Efekt%C3%ADvnos%C5%A5_algoritmu" title="Efektívnosť algoritmu – Slovak" lang="sk" hreflang="sk" data-title="Efektívnosť algoritmu" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%B0%D0%BC%D1%81%D0%BA%D0%B0_%D0%B5%D1%84%D0%B8%D0%BA%D0%B0%D1%81%D0%BD%D0%BE%D1%81%D1%82" title="Алгоритамска ефикасност – Serbian" lang="sr" hreflang="sr" data-title="Алгоритамска ефикасност" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%95%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%96%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83" title="Ефективність алгоритму – Ukrainian" lang="uk" hreflang="uk" data-title="Ефективність алгоритму" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E6%BC%94%E7%AE%97%E6%B3%95%E6%95%88%E7%8E%87" title="演算法效率 – Cantonese" lang="yue" hreflang="yue" data-title="演算法效率" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95%E6%95%88%E7%8E%87" title="算法效率 – Chinese" lang="zh" hreflang="zh" data-title="算法效率" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1296251#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Algorithmic_efficiency" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Algorithmic_efficiency" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Algorithmic_efficiency"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Algorithmic_efficiency"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Algorithmic_efficiency" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Algorithmic_efficiency" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&oldid=1272259821" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Algorithmic_efficiency&id=1272259821&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FAlgorithmic_efficiency"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FAlgorithmic_efficiency"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Algorithmic_efficiency&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Algorithmic_efficiency&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1296251" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Algorithmic_efficiency" title="Special:EditPage/Algorithmic efficiency">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Algorithmic+efficiency%22">"Algorithmic efficiency"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Algorithmic+efficiency%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Algorithmic+efficiency%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Algorithmic+efficiency%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Algorithmic+efficiency%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Algorithmic+efficiency%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">January 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Tone plainlinks metadata ambox ambox-style ambox-Tone" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article's <b>tone or style may not reflect the <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">encyclopedic tone</a> used on Wikipedia</b>.<span class="hide-when-compact"> See Wikipedia's <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">guide to writing better articles</a> for suggestions.</span> <span class="date-container"><i>(<span class="date">January 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Property of an algorithm</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with optimization, which is discussed in <a href="/wiki/Program_optimization" title="Program optimization">program optimization</a>, <a href="/wiki/Optimizing_compiler" title="Optimizing compiler">optimizing compiler</a>, <a href="/wiki/Loop_optimization" title="Loop optimization">loop optimization</a>, <a href="/wiki/Object_code_optimizer" title="Object code optimizer">object code optimizer</a>, etc..</div> <p> In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, <b>algorithmic efficiency</b> is a property of an <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> which relates to the amount of <a href="/wiki/Computational_resource" title="Computational resource">computational resources</a> used by the algorithm. Algorithmic efficiency can be thought of as analogous to engineering <a href="/wiki/Productivity" title="Productivity">productivity</a> for a repeating or continuous process. </p><p>For maximum efficiency it is desirable to minimize resource usage. However, different resources such as <a href="/wiki/Time_complexity" title="Time complexity">time</a> and <a href="/wiki/Space_complexity" title="Space complexity">space</a> complexity cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important. </p><p>For example, <a href="/wiki/Bubble_sort" title="Bubble sort">bubble sort</a> and <a href="/wiki/Timsort" title="Timsort">timsort</a> are both <a href="/wiki/Sorting_algorithm" title="Sorting algorithm">algorithms to sort a list</a> of items from smallest to largest. Bubble sort organizes the list in time proportional to the number of elements squared (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle O(n^{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5982eaab0c0dfc3f9f0bd9380db63a9e0f6da999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.009ex;" alt="{\textstyle O(n^{2})}"></span>, see <a href="/wiki/Big_O_notation" title="Big O notation">Big O notation</a>), but only requires a small amount of extra <a href="/wiki/Computer_memory" title="Computer memory">memory</a> which is constant with respect to the length of the list (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55a2cd47ca6554fafc21bbef3331256c7e1631ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\textstyle O(1)}"></span>). Timsort sorts the list in time <a href="/wiki/Linearithmic" class="mw-redirect" title="Linearithmic">linearithmic</a> (proportional to a quantity times its logarithm) in the list's length (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e300e6b542c2c33ac12df0f02c5047db8ee8e1ca" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\textstyle O(n\log n)}"></span>), but has a space requirement <a href="/wiki/Proportionality_(mathematics)" title="Proportionality (mathematics)">linear</a> in the length of the list (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e73234cd485b947e68d1d78823313db65ef226d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\textstyle O(n)}"></span>). If large lists must be sorted at high speed for a given application, timsort is a better choice; however, if minimizing the <a href="/wiki/Memory_footprint" title="Memory footprint">memory footprint</a> of the sorting is more important, bubble sort is a better choice. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Background">Background</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=1" title="Edit section: Background"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The importance of efficiency with respect to time was emphasized by <a href="/wiki/Ada_Lovelace" title="Ada Lovelace">Ada Lovelace</a> in 1843 as applied to <a href="/wiki/Charles_Babbage" title="Charles Babbage">Charles Babbage</a>'s mechanical analytical engine: </p> <blockquote><p>"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></p></blockquote> <p>Early <a href="/wiki/Electronic_computer" class="mw-redirect" title="Electronic computer">electronic computers</a> had both limited <a href="/wiki/Clock_cycle" class="mw-redirect" title="Clock cycle">speed</a> and limited <a href="/wiki/Random_access_memory" class="mw-redirect" title="Random access memory">random access memory</a>. Therefore, a <a href="/wiki/Space%E2%80%93time_trade-off" class="mw-redirect" title="Space–time trade-off">space–time trade-off</a> occurred. A <a href="/wiki/Task_(computing)" title="Task (computing)">task</a> could use a fast algorithm using a lot of memory, or it could use a slow algorithm using little memory. The engineering trade-off was therefore to use the fastest algorithm that could fit in the available memory. </p><p>Modern computers are significantly faster than early computers and have a much larger amount of memory available (<a href="/wiki/Orders_of_magnitude_(computing)" class="mw-redirect" title="Orders of magnitude (computing)">gigabytes instead of kilobytes</a>). Nevertheless, <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a> emphasized that efficiency is still an important consideration: </p> <blockquote><p> "In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering"<sup id="cite_ref-Knuth1974_2-0" class="reference"><a href="#cite_note-Knuth1974-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></p></blockquote> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=2" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level. Roughly speaking, 'acceptable' means: it will run in a reasonable amount of time or space on an available computer, typically as a <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">function</a> of the size of the input. Since the 1950s computers have seen dramatic increases in both the available computational power and in the available amount of memory, so current acceptable levels would have been unacceptable even 10 years ago. In fact, thanks to the <a href="/wiki/Moore%27s_law" title="Moore's law">approximate doubling of computer power every 2 years</a>, tasks that are acceptably efficient on modern <a href="/wiki/Smartphone" title="Smartphone">smartphones</a> and <a href="/wiki/Embedded_system" title="Embedded system">embedded systems</a> may have been unacceptably inefficient for industrial <a href="/wiki/Server_(computing)" title="Server (computing)">servers</a> 10 years ago. </p><p>Computer manufacturers frequently bring out new models, often with higher <a href="/wiki/Computer_performance" title="Computer performance">performance</a>. Software costs can be quite high, so in some cases the simplest and cheapest way of getting higher performance might be to just buy a faster computer, provided it is <a href="/wiki/Backward_compatibility" title="Backward compatibility">compatible</a> with an existing computer. </p><p>There are many ways in which the resources used by an algorithm can be measured: the two most common measures are speed and memory usage; other measures could include transmission speed, temporary disk usage, long-term disk usage, power consumption, <a href="/wiki/Total_cost_of_ownership" title="Total cost of ownership">total cost of ownership</a>, <a href="/wiki/Response_time_(technology)" title="Response time (technology)">response time</a> to external stimuli, etc. Many of these measures depend on the size of the input to the algorithm, i.e. the amount of data to be processed. They might also depend on the way in which the data is arranged; for example, some <a href="/wiki/Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a> perform poorly on data which is already sorted, or which is sorted in reverse order. </p><p>In practice, there are other factors which can affect the efficiency of an algorithm, such as requirements for accuracy and/or reliability. As detailed below, the way in which an algorithm is implemented can also have a significant effect on actual efficiency, though many aspects of this relate to <a href="/wiki/Optimization_(computer_science)" class="mw-redirect" title="Optimization (computer science)">optimization</a> issues. </p> <div class="mw-heading mw-heading3"><h3 id="Theoretical_analysis">Theoretical analysis</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=3" title="Edit section: Theoretical analysis"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the theoretical <a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">analysis of algorithms</a>, the normal practice is to estimate their complexity in the asymptotic sense. The most commonly used notation to describe resource consumption or "complexity" is <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>'s <a href="/wiki/Big_O_notation" title="Big O notation">Big O notation</a>, representing the complexity of an algorithm as a function of the size of the input <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc6e1f880981346a604257ebcacdef24c0aca2d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}"></span>. Big O notation is an <a href="/wiki/Asymptote" title="Asymptote">asymptotic</a> measure of function complexity, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>O</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> </mrow> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e763b207be3bc51ff39ea77eba50a518a2e76478" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.804ex; height:3.176ex;" alt="{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}"></span> roughly means the time requirement for an algorithm is proportional to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ad18070e494503403daf39398e711c1378348e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}"></span>, omitting <a href="/wiki/Lower-order_terms" class="mw-redirect" title="Lower-order terms">lower-order terms</a> that contribute less than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ad18070e494503403daf39398e711c1378348e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}"></span> to the growth of the function as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc6e1f880981346a604257ebcacdef24c0aca2d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}"></span> <a href="/wiki/Limit_(mathematics)" title="Limit (mathematics)">grows arbitrarily large</a>. This estimate may be misleading when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc6e1f880981346a604257ebcacdef24c0aca2d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}"></span> is small, but is generally sufficiently accurate when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc6e1f880981346a604257ebcacdef24c0aca2d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}"></span> is large as the notation is asymptotic. For example, bubble sort may be faster than <a href="/wiki/Merge_sort" title="Merge sort">merge sort</a> when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a small list. Typically, programmers are interested in algorithms that <a href="/wiki/Scalability" title="Scalability">scale</a> efficiently to large input sizes, and merge sort is preferred over bubble sort for lists of length encountered in most data-intensive programs. </p><p>Some examples of Big O notation applied to algorithms' asymptotic time complexity include: </p> <table class="wikitable"> <tbody><tr> <th>Notation</th> <th>Name</th> <th>Examples </th></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}"></span></td> <td><a href="/wiki/Constant_time" class="mw-redirect" title="Constant time">constant</a></td> <td>Finding the median from a sorted list of measurements; Using a constant-size <a href="/wiki/Lookup_table" title="Lookup table">lookup table</a>; Using a suitable <a href="/wiki/Hash_function" title="Hash function">hash function</a> for looking up an item. </td></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span></td> <td><a href="/wiki/Logarithmic_time" class="mw-redirect" title="Logarithmic time">logarithmic</a></td> <td>Finding an item in a sorted array with a <a href="/wiki/Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search</a> or a balanced search <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a> as well as all operations in a <a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a>. </td></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"></span></td> <td><a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear</a></td> <td>Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two <i>n</i>-bit integers by <a href="/wiki/Ripple_carry_adder" class="mw-redirect" title="Ripple carry adder">ripple carry</a>. </td></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></span></td> <td><a href="/wiki/Linearithmic_time" class="mw-redirect" title="Linearithmic time">linearithmic</a>, loglinear, or quasilinear</td> <td>Performing a <a href="/wiki/Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier transform</a>; <a href="/wiki/Heapsort" title="Heapsort">heapsort</a>, <a href="/wiki/Quicksort" title="Quicksort">quicksort</a> (<a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">best and average case</a>), or <a href="/wiki/Merge_sort" title="Merge sort">merge sort</a> </td></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}"></span></td> <td><a href="/wiki/Quadratic_time" class="mw-redirect" title="Quadratic time">quadratic</a></td> <td><a href="/wiki/Multiplication" title="Multiplication">Multiplying</a> two <i>n</i>-digit numbers by <a href="/wiki/Long_multiplication" class="mw-redirect" title="Long multiplication">a simple algorithm</a>; <a href="/wiki/Bubble_sort" title="Bubble sort">bubble sort</a> (worst case or naive implementation), <a href="/wiki/Shell_sort" class="mw-redirect" title="Shell sort">Shell sort</a>, quicksort (<a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">worst case</a>), <a href="/wiki/Selection_sort" title="Selection sort">selection sort</a> or <a href="/wiki/Insertion_sort" title="Insertion sort">insertion sort</a> </td></tr> <tr> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(c^{n}),\;c>1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <mspace width="thickmathspace" /> <mi>c</mi> <mo>></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(c^{n}),\;c>1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89f4ecbe75f2424973437985768adfe6652b1650" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.755ex; height:2.843ex;" alt="{\displaystyle O(c^{n}),\;c>1}"></span></td> <td><a href="/wiki/Exponential_time" class="mw-redirect" title="Exponential time">exponential</a></td> <td>Finding the optimal (non-<a href="/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms" title="Travelling salesman problem">approximate</a>) solution to the <a href="/wiki/Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a> using <a href="/wiki/Dynamic_programming" title="Dynamic programming">dynamic programming</a>; <a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">determining if two logical statements are equivalent</a> using <a href="/wiki/Brute-force_search" title="Brute-force search">brute-force search</a> </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Measuring_performance">Measuring performance</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=4" title="Edit section: Measuring performance"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For new versions of software or to provide comparisons with competitive systems, <a href="/wiki/Benchmark_(computing)" title="Benchmark (computing)">benchmarks</a> are sometimes used, which assist with gauging an algorithms relative performance. If a new <a href="/wiki/Sorting_algorithm" title="Sorting algorithm">sort algorithm</a> is produced, for example, it can be compared with its predecessors to ensure that at least it is efficient as before with known data, taking into consideration any functional improvements. Benchmarks can be used by customers when comparing various products from alternative suppliers to estimate which product will best suit their specific requirements in terms of functionality and performance. For example, in the <a href="/wiki/Mainframe_computer" title="Mainframe computer">mainframe</a> world certain proprietary <a href="/wiki/Mainframe_sort_merge" title="Mainframe sort merge">sort</a> products from independent software companies such as <a href="/wiki/Syncsort" class="mw-redirect" title="Syncsort">Syncsort</a> compete with products from the major suppliers such as <a href="/wiki/IBM" title="IBM">IBM</a> for speed. </p><p>Some benchmarks provide opportunities for producing an analysis comparing the relative speed of various compiled and interpreted languages for example<sup id="cite_ref-fourmilab.ch_3-0" class="reference"><a href="#cite_note-fourmilab.ch-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> and <a href="/wiki/The_Computer_Language_Benchmarks_Game" title="The Computer Language Benchmarks Game">The Computer Language Benchmarks Game</a> compares the performance of implementations of typical programming problems in several programming languages. </p><p>Even creating "<a href="/wiki/Do_it_yourself" title="Do it yourself">do it yourself</a>" benchmarks can demonstrate the relative performance of different programming languages, using a variety of user specified criteria. This is quite simple, as a "Nine language performance roundup" by Christopher W. Cowell-Shah demonstrates by example.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Implementation_concerns">Implementation concerns</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=5" title="Edit section: Implementation concerns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded,<sup id="cite_ref-KriegelSchubert2016_6-0" class="reference"><a href="#cite_note-KriegelSchubert2016-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> or the choice of a <a href="/wiki/Compiler" title="Compiler">compiler</a> for a particular language, or the <a href="/wiki/Compiler_optimization" class="mw-redirect" title="Compiler optimization">compilation options</a> used, or even the <a href="/wiki/Operating_system" title="Operating system">operating system</a> being used. In many cases a language implemented by an <a href="/wiki/Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> may be much slower than a language implemented by a compiler.<sup id="cite_ref-fourmilab.ch_3-1" class="reference"><a href="#cite_note-fourmilab.ch-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> See the articles on <a href="/wiki/Just-in-time_compilation" title="Just-in-time compilation">just-in-time compilation</a> and <a href="/wiki/Interpreted_language" class="mw-redirect" title="Interpreted language">interpreted languages</a>. </p><p>There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include <a href="/wiki/Data_alignment" class="mw-redirect" title="Data alignment">data alignment</a>, <a href="/wiki/Granularity#Data_granularity" title="Granularity">data granularity</a>, <a href="/wiki/Locality_of_reference" title="Locality of reference">cache locality</a>, <a href="/wiki/Cache_coherence" title="Cache coherence">cache coherency</a>, <a href="/wiki/Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collection</a>, <a href="/wiki/Instruction-level_parallelism" title="Instruction-level parallelism">instruction-level parallelism</a>, <a href="/wiki/Multithreading_(disambiguation)" class="mw-redirect mw-disambig" title="Multithreading (disambiguation)">multi-threading</a> (at either a hardware or software level), <a href="/wiki/Simultaneous_multithreading" title="Simultaneous multithreading">simultaneous multitasking</a>, and <a href="/wiki/Subroutine" class="mw-redirect" title="Subroutine">subroutine</a> calls.<sup id="cite_ref-steele1997_7-0" class="reference"><a href="#cite_note-steele1997-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p><p>Some processors have capabilities for <a href="/wiki/Vector_processor" title="Vector processor">vector processing</a>, which allow a <a href="/wiki/SIMD" class="mw-redirect" title="SIMD">single instruction to operate on multiple operands</a>; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of <a href="/wiki/Parallel_computing" title="Parallel computing">parallel processing</a>, or they could be easily reconfigured. As <a href="/wiki/Parallel_computing" title="Parallel computing">parallel</a> and <a href="/wiki/Distributed_computing" title="Distributed computing">distributed computing</a> grow in importance in the late 2010s, more investments are being made into efficient <a href="/wiki/High-level_programming_language" title="High-level programming language">high-level</a> <a href="/wiki/Application_programming_interface" class="mw-redirect" title="Application programming interface">APIs</a> for parallel and distributed computing systems such as <a href="/wiki/CUDA" title="CUDA">CUDA</a>, <a href="/wiki/TensorFlow" title="TensorFlow">TensorFlow</a>, <a href="/wiki/Apache_Hadoop" title="Apache Hadoop">Hadoop</a>, <a href="/wiki/OpenMP" title="OpenMP">OpenMP</a> and <a href="/wiki/Message_Passing_Interface" title="Message Passing Interface">MPI</a>. </p><p>Another problem which can arise in programming is that processors compatible with the same <a href="/wiki/Instruction_set_architecture" title="Instruction set architecture">instruction set</a> (such as <a href="/wiki/X86-64" title="X86-64">x86-64</a> or <a href="/wiki/ARM_architecture" class="mw-redirect" title="ARM architecture">ARM</a>) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to <a href="/wiki/Optimizing_compiler" title="Optimizing compiler">optimizing compilers</a>, which must have extensive knowledge of the specific <a href="/wiki/Central_processing_unit" title="Central processing unit">CPU</a> and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to <a href="/wiki/Software_emulation" class="mw-redirect" title="Software emulation">emulate</a> instructions not supported on a compilation target platform, forcing it to <a href="/wiki/Code_generation_(compiler)" title="Code generation (compiler)">generate code</a> or <a href="/wiki/Linking_(computing)" class="mw-redirect" title="Linking (computing)">link</a> an external <a href="/wiki/Library_(computing)" title="Library (computing)">library call</a> to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in <a href="/wiki/Embedded_system" title="Embedded system">embedded systems</a> with respect to <a href="/wiki/Floating-point_arithmetic" title="Floating-point arithmetic">floating-point arithmetic</a>, where small and <a href="/wiki/Low-power_computing" class="mw-redirect" title="Low-power computing">low-power</a> <a href="/wiki/Microcontroller" title="Microcontroller">microcontrollers</a> often lack hardware support for floating-point arithmetic and thus require computationally expensive software routines to produce floating point calculations. </p> <div class="mw-heading mw-heading2"><h2 id="Measures_of_resource_usage">Measures of resource usage</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=6" title="Edit section: Measures of resource usage"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Measures are normally expressed as a function of the size of the input <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle {n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="false" scriptlevel="1"> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \scriptstyle {n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4108828bc4534897ce3e5e92aba9d8c5de06392a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.986ex; height:1.343ex;" alt="{\displaystyle \scriptstyle {n}}"></span>. </p><p>The two most common measures are: </p> <ul><li><i>Time</i>: how long does the algorithm take to complete?</li> <li><i>Space</i>: how much working memory (typically RAM) is needed by the algorithm? This has two aspects: the amount of memory needed by the code (auxiliary space usage), and the amount of memory needed for the data on which the code operates (intrinsic space usage).</li></ul> <p>For computers whose power is supplied by a battery (e.g. <a href="/wiki/Laptop" title="Laptop">laptops</a> and <a href="/wiki/Smartphone" title="Smartphone">smartphones</a>), or for very long/large calculations (e.g. <a href="/wiki/Supercomputer" title="Supercomputer">supercomputers</a>), other measures of interest are: </p> <ul><li><i>Direct power consumption</i>: power needed directly to operate the computer.</li> <li><i>Indirect power consumption</i>: power needed for cooling, lighting, etc.</li></ul> <p>As of 2018<sup class="plainlinks noexcerpt noprint asof-tag update" style="display:none;"><a class="external text" href="https://en.wikipedia.org/w/index.php?title=Algorithmic_efficiency&action=edit">[update]</a></sup>, power consumption is growing as an important metric for computational tasks of all types and at all scales ranging from <a href="/wiki/Embedded_system" title="Embedded system">embedded</a> <a href="/wiki/Internet_of_things" title="Internet of things">Internet of things</a> devices to <a href="/wiki/System-on-chip" class="mw-redirect" title="System-on-chip">system-on-chip</a> devices to <a href="/wiki/Server_farm" title="Server farm">server farms</a>. This trend is often referred to as <a href="/wiki/Green_computing" title="Green computing">green computing</a>. </p><p>Less common measures of computational efficiency may also be relevant in some cases: </p> <ul><li><i>Transmission size</i>: bandwidth could be a limiting factor. <a href="/wiki/Data_compression" title="Data compression">Data compression</a> can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. <a href="/wiki/File:Google.png" title="File:Google.png">Google logo</a>) can result in transmitting tens of thousands of bytes (48K in this case) compared with transmitting six bytes for the text "Google". This is important for <a href="/wiki/I/O_bound_computing" class="mw-redirect" title="I/O bound computing">I/O bound computing</a> tasks.</li> <li><i>External space</i>: space needed on a disk or other external memory device; this could be for temporary storage while the algorithm is being carried out, or it could be long-term storage needed to be carried forward for future reference.</li> <li><i>Response time</i> (<a href="/wiki/Latency_(engineering)" title="Latency (engineering)">latency</a>): this is particularly relevant in a <a href="/wiki/Real-time_computing" title="Real-time computing">real-time application</a> when the computer system must <a href="/wiki/Event-driven_programming" title="Event-driven programming">respond quickly to some external event</a>.</li> <li><i>Total cost of ownership</i>: particularly if a computer is dedicated to one particular algorithm.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Time">Time</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=7" title="Edit section: Time"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="Theory">Theory</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=8" title="Edit section: Theory"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a>, typically using concepts like <a href="/wiki/Time_complexity" title="Time complexity">time complexity</a>, can be used to get an estimate of the running time as a function of the size of the input data. The result is normally expressed using <a href="/wiki/Big_O_notation" title="Big O notation">Big O notation</a>. This is useful for comparing algorithms, especially when a large amount of data is to be processed. More detailed estimates are needed to compare algorithm performance when the amount of data is small, although this is likely to be of less importance. <a href="/wiki/Parallel_algorithm" title="Parallel algorithm">Parallel algorithms</a> may be <a href="/wiki/Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">more difficult to analyze</a>. </p> <div class="mw-heading mw-heading4"><h4 id="Practice">Practice</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=9" title="Edit section: Practice"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Benchmark_(computing)" title="Benchmark (computing)">benchmark</a> can be used to assess the performance of an algorithm in practice. Many programming languages have an available function which provides <a href="/wiki/CPU_time" title="CPU time">CPU time</a> usage. For long-running algorithms the elapsed time could also be of interest. Results should generally be averaged over several tests. </p><p>Run-based profiling can be very sensitive to hardware configuration and the possibility of other programs or tasks running at the same time in a <a href="/wiki/Multi-processing" class="mw-redirect" title="Multi-processing">multi-processing</a> and <a href="/wiki/Multi-programming" class="mw-redirect" title="Multi-programming">multi-programming</a> environment. </p><p>This sort of test also depends heavily on the selection of a particular programming language, compiler, and compiler options, so algorithms being compared must all be implemented under the same conditions. </p> <div class="mw-heading mw-heading3"><h3 id="Space">Space</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=10" title="Edit section: Space"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This section is concerned with use of memory resources (<a href="/wiki/Processor_register" title="Processor register">registers</a>, <a href="/wiki/Cache_(computing)" title="Cache (computing)">cache</a>, <a href="/wiki/Random-access_memory" title="Random-access memory">RAM</a>, <a href="/wiki/Virtual_memory" title="Virtual memory">virtual memory</a>, <a href="/wiki/Auxiliary_memory" class="mw-redirect" title="Auxiliary memory">secondary memory</a>) while the algorithm is being executed. As for time analysis above, <a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">analyze</a> the algorithm, typically using <a href="/wiki/Space_complexity" title="Space complexity">space complexity</a> analysis to get an estimate of the run-time memory needed as a function as the size of the input data. The result is normally expressed using <a href="/wiki/Big_O_notation" title="Big O notation">Big O notation</a>. </p><p>There are up to four aspects of memory usage to consider: </p> <ul><li>The amount of memory needed to hold the code for the algorithm.</li> <li>The amount of memory needed for the <a href="/wiki/Input_(computer_science)" title="Input (computer science)">input data</a>.</li> <li>The amount of memory needed for any <a href="/wiki/Output_(computing)" class="mw-redirect" title="Output (computing)">output data</a>. <ul><li>Some algorithms, such as sorting, often <a href="/wiki/In-place_algorithm" title="In-place algorithm">rearrange the input data</a> and do not need any additional space for output data. This property is referred to as "<a href="/wiki/In-place_algorithm" title="In-place algorithm">in-place</a>" operation.</li></ul></li> <li>The amount of memory needed as working space during the calculation. <ul><li>This includes <a href="/wiki/Local_variable" title="Local variable">local variables</a> and any <a href="/wiki/Local_variables,_recursion_and_reentrancy" class="mw-redirect" title="Local variables, recursion and reentrancy">stack space needed</a> by <a href="/wiki/Function_call" class="mw-redirect" title="Function call">routines called</a> during a calculation; this stack space can be significant for algorithms which use <a href="/wiki/Recursion_(computer_science)" title="Recursion (computer science)">recursive</a> techniques.</li></ul></li></ul> <p>Early electronic computers, and early home computers, had relatively small amounts of working memory. For example, the 1949 <a href="/wiki/Electronic_Delay_Storage_Automatic_Calculator" class="mw-redirect" title="Electronic Delay Storage Automatic Calculator">Electronic Delay Storage Automatic Calculator</a> (EDSAC) had a maximum working memory of 1024 17-bit words, while the 1980 Sinclair <a href="/wiki/ZX80" title="ZX80">ZX80</a> came initially with 1024 8-bit bytes of working memory. In the late 2010s, it is typical for <a href="/wiki/Personal_computer" title="Personal computer">personal computers</a> to have between 4 and 32 <a href="/wiki/Gigabyte" title="Gigabyte">GB</a> of RAM, an increase of over 300 million times as much memory. </p> <div class="mw-heading mw-heading4"><h4 id="Caching_and_memory_hierarchy">Caching and memory hierarchy</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=11" title="Edit section: Caching and memory hierarchy"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="/wiki/Memory_hierarchy" title="Memory hierarchy">Memory hierarchy</a></div> <p>Modern computers can have relatively large amounts of memory (possibly gigabytes), so having to squeeze an algorithm into a confined amount of memory is not the kind of problem it used to be. However, the different types of memory and their relative access speeds can be significant: </p> <ul><li><a href="/wiki/Processor_register" title="Processor register">Processor registers</a>, are the fastest memory with the least amount of space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a <a href="/wiki/CPU_core" class="mw-redirect" title="CPU core">processor core</a>, there are typically on the order of hundreds of bytes or fewer of register availability, although a <a href="/wiki/Register_file" title="Register file">register file</a> may contain more physical registers than <a href="/wiki/Instruction_set_architecture" title="Instruction set architecture">architectural</a> registers defined in the instruction set architecture.</li> <li><a href="/wiki/CPU_cache" title="CPU cache">Cache memory</a> is the second fastest, and second smallest, available in the memory hierarchy. Caches are present in processors such as CPUs or GPUs, where they are typically implemented in <a href="/wiki/Static_random-access_memory" title="Static random-access memory">static RAM</a>, though they can also be found in peripherals such as disk drives. Processor caches often have their own <a href="/wiki/Cache_hierarchy" title="Cache hierarchy">multi-level hierarchy</a>; lower levels are larger, slower and typically <a href="/wiki/Shared_cache" class="mw-redirect" title="Shared cache">shared</a> between <a href="/wiki/Processor_core" class="mw-redirect" title="Processor core">processor cores</a> in <a href="/wiki/Multi-core_processor" title="Multi-core processor">multi-core processors</a>. In order to process operands in cache memory, a <a href="/wiki/Processor_(computing)" title="Processor (computing)">processing unit</a> must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2-10 times slower) with the CPU or GPU's <a href="/wiki/Arithmetic_logic_unit" title="Arithmetic logic unit">arithmetic logic unit</a> or <a href="/wiki/Floating-point_unit" title="Floating-point unit">floating-point unit</a> if in the <a href="/wiki/L1_cache" class="mw-redirect" title="L1 cache">L1 cache</a>.<sup id="cite_ref-CompArc:QuantApp_8-0" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> It is about 10 times slower if there is an L1 <a href="/wiki/Cache_miss" class="mw-redirect" title="Cache miss">cache miss</a> and it must be retrieved from and written to the <a href="/wiki/L2_cache" class="mw-redirect" title="L2 cache">L2 cache</a>, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an <a href="/wiki/L3_cache" class="mw-redirect" title="L3 cache">L3 cache</a>, if present.</li> <li><a href="/wiki/Main_memory" class="mw-redirect" title="Main memory">Main physical memory</a> is most often implemented in <a href="/wiki/Dynamic_RAM" class="mw-redirect" title="Dynamic RAM">dynamic RAM</a> (DRAM). The main memory is much larger (typically <a href="/wiki/Gigabyte" title="Gigabyte">gigabytes</a> compared to ≈8 <a href="/wiki/Megabyte" title="Megabyte">megabytes</a>) than an L3 CPU cache, with read and write latencies typically 10-100 times slower.<sup id="cite_ref-CompArc:QuantApp_8-1" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> As of 2018<sup class="plainlinks noexcerpt noprint asof-tag update" style="display:none;"><a class="external text" href="https://en.wikipedia.org/w/index.php?title=Algorithmic_efficiency&action=edit">[update]</a></sup>, RAM is increasingly implemented <a href="/wiki/System-on-chip" class="mw-redirect" title="System-on-chip">on-chip</a> of processors, as CPU or <a href="/wiki/GPU_memory" class="mw-redirect" title="GPU memory">GPU memory</a>.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (July 2024)">citation needed</span></a></i>]</sup></li> <li><a href="/wiki/Paged_memory" class="mw-redirect" title="Paged memory">Paged memory</a>, often used for <a href="/wiki/Virtual_memory" title="Virtual memory">virtual memory</a> management, is memory stored in <a href="/wiki/Secondary_storage" class="mw-redirect" title="Secondary storage">secondary storage</a> such as a <a href="/wiki/Hard_disk" class="mw-redirect" title="Hard disk">hard disk</a>, and is an extension to the <a href="/wiki/Memory_hierarchy" title="Memory hierarchy">memory hierarchy</a> which allows use of a potentially larger storage space, at the cost of much higher latency, typically around 1000 times slower than a <a href="/wiki/Cache_miss" class="mw-redirect" title="Cache miss">cache miss</a> for a value in RAM.<sup id="cite_ref-CompArc:QuantApp_8-2" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its <a href="/wiki/Time-space_tradeoff" class="mw-redirect" title="Time-space tradeoff">time-space tradeoff</a> and enabling the usage of <a href="/wiki/Virtual_machine" title="Virtual machine">virtual machines</a>.<sup id="cite_ref-CompArc:QuantApp_8-3" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> Cache misses from main memory are called <a href="/wiki/Page_fault" title="Page fault">page faults</a>, and incur huge performance penalties on programs.</li></ul> <p>An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to paging. Because of this, <a href="/wiki/Cache_replacement_policies" title="Cache replacement policies">cache replacement policies</a> are extremely important to high-performance computing, as are <a href="/wiki/Cache-aware_model" class="mw-redirect" title="Cache-aware model">cache-aware programming</a> and <a href="/wiki/Data_alignment" class="mw-redirect" title="Data alignment">data alignment</a>. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another. </p><p>In the early days of electronic computing, if an algorithm and its data would not fit in main memory then the algorithm could not be used. Nowadays the use of virtual memory appears to provide much more memory, but at the cost of performance. Much higher speed can be obtained if an algorithm and its data fit in cache memory; in this case minimizing space will also help minimize time. This is called the <a href="/wiki/Principle_of_locality" title="Principle of locality">principle of locality</a>, and can be subdivided into <a href="/wiki/Locality_of_reference" title="Locality of reference">locality of reference</a>, <a href="/wiki/Spatial_locality" class="mw-redirect" title="Spatial locality">spatial locality</a>, and <a href="/wiki/Temporal_locality" class="mw-redirect" title="Temporal locality">temporal locality</a>. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a>—how to determine the resources needed by an algorithm</li> <li><a href="/wiki/Benchmark_(computing)" title="Benchmark (computing)">Benchmark</a>—a method for measuring comparative execution times in defined cases</li> <li><a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case">Best, worst and average case</a>—considerations for estimating execution times in three scenarios</li> <li><a href="/wiki/Compiler_optimization" class="mw-redirect" title="Compiler optimization">Compiler optimization</a>—compiler-derived optimization</li> <li><a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li> <li><a href="/wiki/Computer_performance" title="Computer performance">Computer performance</a>—computer hardware metrics</li> <li><a href="/wiki/Empirical_algorithmics" title="Empirical algorithmics">Empirical algorithmics</a>—the practice of using empirical methods to study the behavior of algorithms</li> <li><a href="/wiki/Program_optimization" title="Program optimization">Program optimization</a></li> <li><a href="/wiki/Profiling_(computer_programming)" title="Profiling (computer programming)">Performance analysis</a>—methods of measuring actual performance of an algorithm at run-time</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Algorithmic_efficiency&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFGreen" class="citation cs2">Green, Christopher, <a rel="nofollow" class="external text" href="http://psychclassics.yorku.ca/Lovelace/lovelace.htm"><i>Classics in the History of Psychology</i></a><span class="reference-accessdate">, retrieved <span class="nowrap">19 May</span> 2013</span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Classics+in+the+History+of+Psychology&rft.aulast=Green&rft.aufirst=Christopher&rft_id=http%3A%2F%2Fpsychclassics.yorku.ca%2FLovelace%2Flovelace.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-Knuth1974-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Knuth1974_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnuth1974" class="citation cs2">Knuth, Donald (1974), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090824073244/http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf">"Structured Programming with go-to Statements"</a> <span class="cs1-format">(PDF)</span>, <i>Computing Surveys</i>, <b>6</b> (4): <span class="nowrap">261–</span>301, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.6084">10.1.1.103.6084</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F356635.356640">10.1145/356635.356640</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207630080">207630080</a>, archived from <a rel="nofollow" class="external text" href="http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 24 August 2009<span class="reference-accessdate">, retrieved <span class="nowrap">19 May</span> 2013</span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computing+Surveys&rft.atitle=Structured+Programming+with+go-to+Statements&rft.volume=6&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E261-%3C%2Fspan%3E301&rft.date=1974&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.103.6084%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207630080%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F356635.356640&rft.aulast=Knuth&rft.aufirst=Donald&rft_id=http%3A%2F%2Fpplab.snu.ac.kr%2Fcourses%2Fadv_pl05%2Fpapers%2Fp261-knuth.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-fourmilab.ch-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-fourmilab.ch_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-fourmilab.ch_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html">"Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason)"</a>. Fourmilab.ch. 4 August 2005<span class="reference-accessdate">. Retrieved <span class="nowrap">14 December</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Floating+Point+Benchmark%3A+Comparing+Languages+%28Fourmilog%3A+None+Dare+Call+It+Reason%29&rft.pub=Fourmilab.ch&rft.date=2005-08-04&rft_id=http%3A%2F%2Fwww.fourmilab.ch%2Ffourmilog%2Farchives%2F2005-08%2F000567.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2">"Whetstone Benchmark History"</a>. Roylongbottom.org.uk<span class="reference-accessdate">. Retrieved <span class="nowrap">14 December</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Whetstone+Benchmark+History&rft.pub=Roylongbottom.org.uk&rft_id=http%3A%2F%2Fwww.roylongbottom.org.uk%2Fwhetstone.htm%23anchorPC2&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOSNews_Staff" class="citation web cs1">OSNews Staff. <a rel="nofollow" class="external text" href="http://www.osnews.com/story/5602">"Nine Language Performance Round-up: Benchmarking Math & File I/O"</a>. <i>osnews.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">18 September</span> 2018</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=osnews.com&rft.atitle=Nine+Language+Performance+Round-up%3A+Benchmarking+Math+%26+File+I%2FO&rft.au=OSNews+Staff&rft_id=http%3A%2F%2Fwww.osnews.com%2Fstory%2F5602&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-KriegelSchubert2016-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-KriegelSchubert2016_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKriegelSchubertZimek2016" class="citation journal cs1"><a href="/wiki/Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, Hans-Peter</a>; Schubert, Erich; <a href="/wiki/Arthur_Zimek" title="Arthur Zimek">Zimek, Arthur</a> (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". <i>Knowledge and Information Systems</i>. <b>52</b> (2): <span class="nowrap">341–</span>378. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10115-016-1004-2">10.1007/s10115-016-1004-2</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0219-1377">0219-1377</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:40772241">40772241</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Knowledge+and+Information+Systems&rft.atitle=The+%28black%29+art+of+runtime+evaluation%3A+Are+we+comparing+algorithms+or+implementations%3F&rft.volume=52&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E341-%3C%2Fspan%3E378&rft.date=2016&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A40772241%23id-name%3DS2CID&rft.issn=0219-1377&rft_id=info%3Adoi%2F10.1007%2Fs10115-016-1004-2&rft.aulast=Kriegel&rft.aufirst=Hans-Peter&rft.au=Schubert%2C+Erich&rft.au=Zimek%2C+Arthur&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> <li id="cite_note-steele1997-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-steele1997_7-0">^</a></b></span> <span class="reference-text">Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.<a rel="nofollow" class="external autonumber" href="http://dspace.mit.edu/handle/1721.1/5753">[1]</a></span> </li> <li id="cite_note-CompArc:QuantApp-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-CompArc:QuantApp_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHennessyPattersonAsanovićBakos2011" class="citation book cs1">Hennessy, John L; Patterson, David A; <a href="/wiki/Krste_Asanovi%C4%87" title="Krste Asanović">Asanović, Krste</a>; Bakos, Jason D; Colwell, Robert P; Bhattacharjee, Abhishek; Conte, Thomas M; Duato, José; Franklin, Diana; Goldberg, David; <a href="/wiki/Norman_Jouppi" title="Norman Jouppi">Jouppi, Norman P</a>; Li, Sheng; Muralimanohar, Naveen; Peterson, Gregory D; Pinkston, Timothy Mark; Ranganathan, Prakash; Wood, David Allen; Young, Clifford; Zaky, Amr (2011). <i>Computer Architecture: a Quantitative Approach</i> (Sixth ed.). Elsevier Science. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0128119051" title="Special:BookSources/978-0128119051"><bdi>978-0128119051</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/983459758">983459758</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computer+Architecture%3A+a+Quantitative+Approach&rft.edition=Sixth&rft.pub=Elsevier+Science&rft.date=2011&rft_id=info%3Aoclcnum%2F983459758&rft.isbn=978-0128119051&rft.aulast=Hennessy&rft.aufirst=John+L&rft.au=Patterson%2C+David+A&rft.au=Asanovi%C4%87%2C+Krste&rft.au=Bakos%2C+Jason+D&rft.au=Colwell%2C+Robert+P&rft.au=Bhattacharjee%2C+Abhishek&rft.au=Conte%2C+Thomas+M&rft.au=Duato%2C+Jos%C3%A9&rft.au=Franklin%2C+Diana&rft.au=Goldberg%2C+David&rft.au=Jouppi%2C+Norman+P&rft.au=Li%2C+Sheng&rft.au=Muralimanohar%2C+Naveen&rft.au=Peterson%2C+Gregory+D&rft.au=Pinkston%2C+Timothy+Mark&rft.au=Ranganathan%2C+Prakash&rft.au=Wood%2C+David+Allen&rft.au=Young%2C+Clifford&rft.au=Zaky%2C+Amr&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlgorithmic+efficiency" class="Z3988"></span></span> </li> </ol></div></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Computer_science1028" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Computer_science" title="Template:Computer science"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Computer_science" title="Template talk:Computer science"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Computer_science" title="Special:EditPage/Template:Computer science"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Computer_science1028" style="font-size:114%;margin:0 4em"><a href="/wiki/Computer_science" title="Computer science">Computer science</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>Note: This template roughly follows the 2012 <a href="/wiki/ACM_Computing_Classification_System" title="ACM Computing Classification System">ACM Computing Classification System</a>.</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Printed_circuit_board" title="Printed circuit board">Printed circuit board</a></li> <li><a href="/wiki/Peripheral" title="Peripheral">Peripheral</a></li> <li><a href="/wiki/Integrated_circuit" title="Integrated circuit">Integrated circuit</a></li> <li><a href="/wiki/Very_Large_Scale_Integration" class="mw-redirect" title="Very Large Scale Integration">Very Large Scale Integration</a></li> <li><a href="/wiki/System_on_a_chip" title="System on a chip">Systems on Chip (SoCs)</a></li> <li><a href="/wiki/Green_computing" title="Green computing">Energy consumption (Green computing)</a></li> <li><a href="/wiki/Electronic_design_automation" title="Electronic design automation">Electronic design automation</a></li> <li><a href="/wiki/Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li> <li><a href="/wiki/Processor_(computing)" title="Processor (computing)">Processor</a></li> <li><a href="/wiki/List_of_computer_size_categories" title="List of computer size categories">Size</a> / <a href="/wiki/Form_factor_(design)" title="Form factor (design)">Form</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Computer systems organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Computer_architecture" title="Computer architecture">Computer architecture</a></li> <li><a href="/wiki/Computational_complexity" title="Computational complexity">Computational complexity</a></li> <li><a href="/wiki/Dependability" title="Dependability">Dependability</a></li> <li><a href="/wiki/Embedded_system" title="Embedded system">Embedded system</a></li> <li><a href="/wiki/Real-time_computing" title="Real-time computing">Real-time computing</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computer_network" title="Computer network">Networks</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Network_architecture" title="Network architecture">Network architecture</a></li> <li><a href="/wiki/Network_protocol" class="mw-redirect" title="Network protocol">Network protocol</a></li> <li><a href="/wiki/Networking_hardware" title="Networking hardware">Network components</a></li> <li><a href="/wiki/Network_scheduler" title="Network scheduler">Network scheduler</a></li> <li><a href="/wiki/Network_performance" title="Network performance">Network performance evaluation</a></li> <li><a href="/wiki/Network_service" title="Network service">Network service</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Interpreter_(computing)" title="Interpreter (computing)">Interpreter</a></li> <li><a href="/wiki/Middleware" title="Middleware">Middleware</a></li> <li><a href="/wiki/Virtual_machine" title="Virtual machine">Virtual machine</a></li> <li><a href="/wiki/Operating_system" title="Operating system">Operating system</a></li> <li><a href="/wiki/Software_quality" title="Software quality">Software quality</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Programming_language_theory" title="Programming language theory">Software notations</a> and <a href="/wiki/Programming_tool" title="Programming tool">tools</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Programming_paradigm" title="Programming paradigm">Programming paradigm</a></li> <li><a href="/wiki/Programming_language" title="Programming language">Programming language</a></li> <li><a href="/wiki/Compiler_construction" class="mw-redirect" title="Compiler construction">Compiler</a></li> <li><a href="/wiki/Domain-specific_language" title="Domain-specific language">Domain-specific language</a></li> <li><a href="/wiki/Modeling_language" title="Modeling language">Modeling language</a></li> <li><a href="/wiki/Software_framework" title="Software framework">Software framework</a></li> <li><a href="/wiki/Integrated_development_environment" title="Integrated development environment">Integrated development environment</a></li> <li><a href="/wiki/Software_configuration_management" title="Software configuration management">Software configuration management</a></li> <li><a href="/wiki/Library_(computing)" title="Library (computing)">Software library</a></li> <li><a href="/wiki/Software_repository" title="Software repository">Software repository</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Software_development" title="Software development">Software development</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Control_variable_(programming)" class="mw-redirect" title="Control variable (programming)">Control variable</a></li> <li><a href="/wiki/Software_development_process" title="Software development process">Software development process</a></li> <li><a href="/wiki/Requirements_analysis" title="Requirements analysis">Requirements analysis</a></li> <li><a href="/wiki/Software_design" title="Software design">Software design</a></li> <li><a href="/wiki/Software_construction" title="Software construction">Software construction</a></li> <li><a href="/wiki/Software_deployment" title="Software deployment">Software deployment</a></li> <li><a href="/wiki/Software_engineering" title="Software engineering">Software engineering</a></li> <li><a href="/wiki/Software_maintenance" title="Software maintenance">Software maintenance</a></li> <li><a href="/wiki/Programming_team" title="Programming team">Programming team</a></li> <li><a href="/wiki/Open-source_software" title="Open-source software">Open-source model</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Theory_of_computation" title="Theory of computation">Theory of computation</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Model_of_computation" title="Model of computation">Model of computation</a> <ul><li><a href="/wiki/Stochastic_computing" title="Stochastic computing">Stochastic</a></li></ul></li> <li><a href="/wiki/Formal_language" title="Formal language">Formal language</a></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata theory</a></li> <li><a href="/wiki/Computability_theory" title="Computability theory">Computability theory</a></li> <li><a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li> <li><a href="/wiki/Logic_in_computer_science" title="Logic in computer science">Logic</a></li> <li><a href="/wiki/Semantics_(computer_science)" title="Semantics (computer science)">Semantics</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Algorithm" title="Algorithm">Algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Algorithm_design" class="mw-redirect" title="Algorithm design">Algorithm design</a></li> <li><a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a></li> <li><a class="mw-selflink selflink">Algorithmic efficiency</a></li> <li><a href="/wiki/Randomized_algorithm" title="Randomized algorithm">Randomized algorithm</a></li> <li><a href="/wiki/Computational_geometry" title="Computational geometry">Computational geometry</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mathematics of <a href="/wiki/Computing" title="Computing">computing</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Discrete_mathematics" title="Discrete mathematics">Discrete mathematics</a></li> <li><a href="/wiki/Probability" title="Probability">Probability</a></li> <li><a href="/wiki/Statistics" title="Statistics">Statistics</a></li> <li><a href="/wiki/Mathematical_software" title="Mathematical software">Mathematical software</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a></li> <li><a href="/wiki/Mathematical_analysis" title="Mathematical analysis">Mathematical analysis</a></li> <li><a href="/wiki/Numerical_analysis" title="Numerical analysis">Numerical analysis</a></li> <li><a href="/wiki/Theoretical_computer_science" title="Theoretical computer science">Theoretical computer science</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Information_system" title="Information system">Information systems</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Database" title="Database">Database management system</a></li> <li><a href="/wiki/Computer_data_storage" title="Computer data storage">Information storage systems</a></li> <li><a href="/wiki/Enterprise_information_system" title="Enterprise information system">Enterprise information system</a></li> <li><a href="/wiki/Social_software" title="Social software">Social information systems</a></li> <li><a href="/wiki/Geographic_information_system" title="Geographic information system">Geographic information system</a></li> <li><a href="/wiki/Decision_support_system" title="Decision support system">Decision support system</a></li> <li><a href="/wiki/Process_control" class="mw-redirect" title="Process control">Process control system</a></li> <li><a href="/wiki/Multimedia_database" title="Multimedia database">Multimedia information system</a></li> <li><a href="/wiki/Data_mining" title="Data mining">Data mining</a></li> <li><a href="/wiki/Digital_library" title="Digital library">Digital library</a></li> <li><a href="/wiki/Computing_platform" title="Computing platform">Computing platform</a></li> <li><a href="/wiki/Digital_marketing" title="Digital marketing">Digital marketing</a></li> <li><a href="/wiki/World_Wide_Web" title="World Wide Web">World Wide Web</a></li> <li><a href="/wiki/Information_retrieval" title="Information retrieval">Information retrieval</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computer_security" title="Computer security">Security</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cryptography" title="Cryptography">Cryptography</a></li> <li><a href="/wiki/Formal_methods" title="Formal methods">Formal methods</a></li> <li><a href="/wiki/Security_hacker" title="Security hacker">Security hacker</a></li> <li><a href="/wiki/Security_service_(telecommunication)" title="Security service (telecommunication)">Security services</a></li> <li><a href="/wiki/Intrusion_detection_system" title="Intrusion detection system">Intrusion detection system</a></li> <li><a href="/wiki/Hardware_security" title="Hardware security">Hardware security</a></li> <li><a href="/wiki/Network_security" title="Network security">Network security</a></li> <li><a href="/wiki/Information_security" title="Information security">Information security</a></li> <li><a href="/wiki/Application_security" title="Application security">Application security</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Human%E2%80%93computer_interaction" title="Human–computer interaction">Human–computer interaction</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Interaction_design" title="Interaction design">Interaction design</a></li> <li><a href="/wiki/Social_computing" title="Social computing">Social computing</a></li> <li><a href="/wiki/Ubiquitous_computing" title="Ubiquitous computing">Ubiquitous computing</a></li> <li><a href="/wiki/Visualization_(graphics)" title="Visualization (graphics)">Visualization</a></li> <li><a href="/wiki/Computer_accessibility" title="Computer accessibility">Accessibility</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Concurrent_computing" title="Concurrent computing">Concurrent computing</a></li> <li><a href="/wiki/Parallel_computing" title="Parallel computing">Parallel computing</a></li> <li><a href="/wiki/Distributed_computing" title="Distributed computing">Distributed computing</a></li> <li><a href="/wiki/Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></li> <li><a href="/wiki/Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Artificial_intelligence" title="Artificial intelligence">Artificial intelligence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Natural_language_processing" title="Natural language processing">Natural language processing</a></li> <li><a href="/wiki/Knowledge_representation_and_reasoning" title="Knowledge representation and reasoning">Knowledge representation and reasoning</a></li> <li><a href="/wiki/Computer_vision" title="Computer vision">Computer vision</a></li> <li><a href="/wiki/Automated_planning_and_scheduling" title="Automated planning and scheduling">Automated planning and scheduling</a></li> <li><a href="/wiki/Mathematical_optimization" title="Mathematical optimization">Search methodology</a></li> <li><a href="/wiki/Control_theory" title="Control theory">Control method</a></li> <li><a href="/wiki/Philosophy_of_artificial_intelligence" title="Philosophy of artificial intelligence">Philosophy of artificial intelligence</a></li> <li><a href="/wiki/Distributed_artificial_intelligence" title="Distributed artificial intelligence">Distributed artificial intelligence</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Machine_learning" title="Machine learning">Machine learning</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Supervised_learning" title="Supervised learning">Supervised learning</a></li> <li><a href="/wiki/Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li> <li><a href="/wiki/Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li> <li><a href="/wiki/Multi-task_learning" title="Multi-task learning">Multi-task learning</a></li> <li><a href="/wiki/Cross-validation_(statistics)" title="Cross-validation (statistics)">Cross-validation</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computer_graphics" title="Computer graphics">Graphics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Computer_animation" title="Computer animation">Animation</a></li> <li><a href="/wiki/Extended_reality" title="Extended reality">Extended reality</a> <ul><li><a href="/wiki/Augmented_reality" title="Augmented reality">Augmented</a></li> <li><a href="/wiki/Mixed_reality" title="Mixed reality">Mixed</a></li> <li><a href="/wiki/Virtual_reality" title="Virtual reality">Virtual</a></li></ul></li> <li><a href="/wiki/Rendering_(computer_graphics)" title="Rendering (computer graphics)">Rendering</a></li> <li><a href="/wiki/Photograph_manipulation" title="Photograph manipulation">Photograph manipulation</a></li> <li><a href="/wiki/Graphics_processing_unit" title="Graphics processing unit">Graphics processing unit</a></li> <li><a href="/wiki/Image_compression" title="Image compression">Image compression</a></li> <li><a href="/wiki/Solid_modeling" title="Solid modeling">Solid modeling</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Applied computing</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Quantum_Computing" class="mw-redirect" title="Quantum Computing">Quantum Computing</a></li> <li><a href="/wiki/E-commerce" title="E-commerce">E-commerce</a></li> <li><a href="/wiki/Enterprise_software" title="Enterprise software">Enterprise software</a></li> <li><a href="/wiki/Computational_mathematics" title="Computational mathematics">Computational mathematics</a></li> <li><a href="/wiki/Computational_physics" title="Computational physics">Computational physics</a></li> <li><a href="/wiki/Computational_chemistry" title="Computational chemistry">Computational chemistry</a></li> <li><a href="/wiki/Computational_biology" title="Computational biology">Computational biology</a></li> <li><a href="/wiki/Computational_social_science" title="Computational social science">Computational social science</a></li> <li><a href="/wiki/Computational_engineering" title="Computational engineering">Computational engineering</a></li> <li><a href="/wiki/Template:Differentiable_computing" title="Template:Differentiable computing">Differentiable computing</a></li> <li><a href="/wiki/Health_informatics" title="Health informatics">Computational healthcare</a></li> <li><a href="/wiki/Digital_art" title="Digital art">Digital art</a></li> <li><a href="/wiki/Electronic_publishing" title="Electronic publishing">Electronic publishing</a></li> <li><a href="/wiki/Cyberwarfare" title="Cyberwarfare">Cyberwarfare</a></li> <li><a href="/wiki/Electronic_voting" title="Electronic voting">Electronic voting</a></li> <li><a href="/wiki/Video_game" title="Video game">Video games</a></li> <li><a href="/wiki/Word_processor" title="Word processor">Word processing</a></li> <li><a href="/wiki/Operations_research" title="Operations research">Operations research</a></li> <li><a href="/wiki/Educational_technology" title="Educational technology">Educational technology</a></li> <li><a href="/wiki/Document_management_system" title="Document management system">Document management</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><span class="noviewer" typeof="mw:File"><span title="Category"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/16px-Symbol_category_class.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/23px-Symbol_category_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/31px-Symbol_category_class.svg.png 2x" data-file-width="180" data-file-height="185" /></span></span> <a href="/wiki/Category:Computer_science" title="Category:Computer science">Category</a></li> <li><span class="noviewer" typeof="mw:File"><span title="Outline"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Global_thinking.svg/10px-Global_thinking.svg.png" decoding="async" width="10" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Global_thinking.svg/15px-Global_thinking.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/41/Global_thinking.svg/21px-Global_thinking.svg.png 2x" data-file-width="130" data-file-height="200" /></span></span> <a href="/wiki/Outline_of_computer_science" title="Outline of computer science">Outline</a></li> <li><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/e/e0/Symbol_question.svg/16px-Symbol_question.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/e/e0/Symbol_question.svg/23px-Symbol_question.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/e/e0/Symbol_question.svg/31px-Symbol_question.svg.png 2x" data-file-width="180" data-file-height="185" /></span></span> <a href="/wiki/Template:Glossaries_of_computers" title="Template:Glossaries of computers">Glossaries</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Software_quality258" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Software_quality" title="Template:Software quality"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Software_quality" title="Template talk:Software quality"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Software_quality" title="Special:EditPage/Template:Software quality"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Software_quality258" style="font-size:114%;margin:0 4em"><a href="/wiki/Software_quality" title="Software quality">Software quality</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Qualities</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%;font-weight:normal;">Internal</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Software_sizing" title="Software sizing">Size</a></li> <li><a href="/wiki/Maintainability#Software_engineering" title="Maintainability">Maintainability</a></li> <li><a href="/wiki/Flexibility_(engineering)" title="Flexibility (engineering)">Flexibility</a></li> <li><a href="/wiki/Software_portability" title="Software portability">Portability</a></li> <li><a href="/wiki/Reusability" title="Reusability">Reusability</a></li> <li><a href="/wiki/Computer_programming#Readability_of_source_code" title="Computer programming">Readability</a></li> <li><a href="/wiki/Scalability" title="Scalability">Scalability</a></li> <li><a href="/wiki/Software_testability" title="Software testability">Testability</a></li> <li><a href="/wiki/Understandability" class="mw-redirect" title="Understandability">Understandability</a></li> <li><a href="/wiki/Loose_coupling" title="Loose coupling">Loose coupling</a></li> <li><a href="/wiki/Orthogonality_(programming)" title="Orthogonality (programming)">Orthogonality</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;font-weight:normal;">External</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Usability" title="Usability">Usability</a></li> <li><a href="/wiki/Reliability_engineering" title="Reliability engineering">Reliability</a></li> <li><a href="/wiki/Adaptability" title="Adaptability">Adaptability</a></li> <li><a href="/wiki/Correctness_(computer_science)" title="Correctness (computer science)">Correctness</a></li> <li><a href="/wiki/Accuracy_and_precision" title="Accuracy and precision">Accuracy</a></li> <li><a class="mw-selflink selflink">Efficiency</a></li> <li><a href="/wiki/Robustness_(computer_science)" title="Robustness (computer science)">Robustness</a></li> <li><a href="/wiki/Software_development_security" class="mw-redirect" title="Software development security">Security</a></li> <li><a href="/wiki/Software_system_safety" class="mw-redirect" title="Software system safety">Safety</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Standards and lists</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/ISO/IEC_9126" title="ISO/IEC 9126">ISO/IEC 9126</a></li> <li><a href="/wiki/Non-functional_requirement#Examples" title="Non-functional requirement">Non-functional requirements</a></li> <li><a href="/wiki/List_of_system_quality_attributes" title="List of system quality attributes">List of system quality attributes</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Processes</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Software_quality_management" title="Software quality management">Software quality management</a></li> <li><a href="/wiki/Software_quality_control" title="Software quality control">Software quality control</a></li> <li><a href="/wiki/Software_quality_assurance" title="Software quality assurance">Software quality assurance</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2" style="font-weight:bold;"><div> <ul><li><span class="noviewer" typeof="mw:File"><span title="Category"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/16px-Symbol_category_class.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/23px-Symbol_category_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/31px-Symbol_category_class.svg.png 2x" data-file-width="180" data-file-height="185" /></span></span></li> <li><span class="noviewer" typeof="mw:File"><span title="Commons page"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/12px-Commons-logo.svg.png" decoding="async" width="12" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/18px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/24px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></span></span> <a href="https://commons.wikimedia.org/wiki/Category:Software_quality" class="extiw" title="commons:Category:Software quality">Commons</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox391" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q1296251#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4013585-8">Germany</a></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Algorithmic_efficiency&oldid=1272259821">https://en.wikipedia.org/w/index.php?title=Algorithmic_efficiency&oldid=1272259821</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Analysis_of_algorithms" title="Category:Analysis of algorithms">Analysis of algorithms</a></li><li><a href="/wiki/Category:Computer_performance" title="Category:Computer performance">Computer performance</a></li><li><a href="/wiki/Category:Software_optimization" title="Category:Software optimization">Software optimization</a></li><li><a href="/wiki/Category:Software_quality" title="Category:Software quality">Software quality</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_needing_additional_references_from_January_2024" title="Category:Articles needing additional references from January 2024">Articles needing additional references from January 2024</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_January_2024" title="Category:Wikipedia articles with style issues from January 2024">Wikipedia articles with style issues from January 2024</a></li><li><a href="/wiki/Category:All_articles_with_style_issues" title="Category:All articles with style issues">All articles with style issues</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_February_2023" title="Category:Use dmy dates from February 2023">Use dmy dates from February 2023</a></li><li><a href="/wiki/Category:Articles_containing_potentially_dated_statements_from_2018" title="Category:Articles containing potentially dated statements from 2018">Articles containing potentially dated statements from 2018</a></li><li><a href="/wiki/Category:All_articles_containing_potentially_dated_statements" title="Category:All articles containing potentially dated statements">All articles containing potentially dated statements</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_July_2024" title="Category:Articles with unsourced statements from July 2024">Articles with unsourced statements from July 2024</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 27 January 2025, at 21:00<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Algorithmic_efficiency&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Algorithmic efficiency</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>17 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-558fc7fc45-4mzqh","wgBackendResponseTime":105,"wgPageParseReport":{"limitreport":{"cputime":"0.446","walltime":"0.638","ppvisitednodes":{"value":2155,"limit":1000000},"postexpandincludesize":{"value":82545,"limit":2097152},"templateargumentsize":{"value":2411,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":7,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":54597,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 446.988 1 -total"," 27.21% 121.619 1 Template:Reflist"," 23.05% 103.022 1 Template:More_citations_needed"," 18.28% 81.719 3 Template:Navbox"," 17.40% 77.786 1 Template:Computer_science"," 16.93% 75.689 2 Template:Ambox"," 15.96% 71.359 2 Template:Citation"," 10.29% 46.008 1 Template:Short_description"," 5.32% 23.782 2 Template:Pagetype"," 4.47% 19.960 1 Template:Authority_control"]},"scribunto":{"limitreport-timeusage":{"value":"0.247","limit":"10.000"},"limitreport-memusage":{"value":6353170,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-cf5c698b4-5gjrw","timestamp":"20250220113637","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Algorithmic efficiency","url":"https:\/\/en.wikipedia.org\/wiki\/Algorithmic_efficiency","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1296251","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1296251","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2002-11-08T08:56:54Z","dateModified":"2025-01-27T21:00:56Z","headline":"amount of computational resources used by an algorithm"}</script> </body> </html>