The Perl and Raku Conference 2025: Greenville, South Carolina - June 27-29 Learn more

KAZUHO / cppref-0.09 / orig / complexity.html 

            

              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

              
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"
 lang="en" dir="ltr">
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <title>
    Time Complexity    [C++ Reference]
  </title>
  <meta name="generator" content="DokuWiki Release 2009-12-25c &quot;Lemming&quot;" />
<meta name="robots" content="index,follow" />
<meta name="date" content="2010-03-15T03:48:56-0700" />
<meta name="keywords" content="complexity" />
<link rel="search" type="application/opensearchdescription+xml" href="/wiki/lib/exe/opensearch.php" title="C++ Reference" />
<link rel="start" href="/wiki/" />
<link rel="contents" href="/wiki/complexity?do=index" title="Index" />
<link rel="alternate" type="application/rss+xml" title="Recent Changes" href="/wiki/feed.php" />
<link rel="alternate" type="application/rss+xml" title="Current Namespace" href="/wiki/feed.php?mode=list&amp;ns=" />
<link rel="edit" title="Edit this page" href="/wiki/complexity?do=edit" />
<link rel="alternate" type="text/html" title="Plain HTML" href="/wiki/_export/xhtml/complexity" />
<link rel="alternate" type="text/plain" title="Wiki Markup" href="/wiki/_export/raw/complexity" />
<link rel="canonical" href="http://www.cppreference.com/wiki/complexity" />
<link rel="stylesheet" media="all" type="text/css" href="/wiki/lib/exe/css.php?s=all&amp;t=custom1&amp;tseed=1272971091" />
<link rel="stylesheet" media="screen" type="text/css" href="/wiki/lib/exe/css.php?t=custom1&amp;tseed=1272971091" />
<link rel="stylesheet" media="print" type="text/css" href="/wiki/lib/exe/css.php?s=print&amp;t=custom1&amp;tseed=1272971091" />
<script type="text/javascript" charset="utf-8" ><!--//--><![CDATA[//><!--
var NS='';var JSINFO = {"id":"complexity","namespace":""};
//--><!]]></script>
<script type="text/javascript" charset="utf-8" src="/wiki/lib/exe/js.php?tseed=1272971091" ></script>
  <link rel="shortcut icon" href="/wiki/lib/tpl/custom1/images/favicon.png" />
  </head>
<body>
<div class="dokuwiki">
   
  <div class="stylehead">
    <div class="header">
      <div class="pagename">
        [[<a href="complexity.html"  title="Backlinks">Time Complexity</a>]]
      </div>
      <div class="logo">
        <a href="http://www.cppreference.com"  name="dokuwiki__top" id="dokuwiki__top" accesskey="h" title="[ALT+H]">C++ Reference</a>      </div>
      <div class="clearer"></div>
    </div>
     
     
        <div class="breadcrumbs">
      <span class="bchead">You are here: </span><a href="start.html"  title="start">C++ Reference</a> &raquo; <a href="complexity.html"  title="complexity">Time Complexity</a>    </div>
     
  </div>
<div class="plugin_translation"><span>Translations of this page<sup><a href="localization.html" class="wikilink1" title="localization">?</a></sup>:</span> <ul>  <li><div class="li"><span class="curid"><a href="complexity.html" class="wikilink1" title="complexity">en</a></span></div></li>  <li><div class="li"><a href="br-pt/complexity.html" class="wikilink2" title="br-pt:complexity" rel="nofollow">br-pt</a></div></li>  <li><div class="li"><a href="cn/complexity.html" class="wikilink1" title="cn:complexity">cn</a></div></li>  <li><div class="li"><a href="cz/complexity.html" class="wikilink2" title="cz:complexity" rel="nofollow">cz</a></div></li>  <li><div class="li"><a href="de/complexity.html" class="wikilink2" title="de:complexity" rel="nofollow">de</a></div></li>  <li><div class="li"><a href="es/complexity.html" class="wikilink1" title="es:complexity">es</a></div></li>  <li><div class="li"><a href="fr/complexity.html" class="wikilink1" title="fr:complexity">fr</a></div></li>  <li><div class="li"><a href="it/complexity.html" class="wikilink1" title="it:complexity">it</a></div></li>  <li><div class="li"><a href="jp/complexity.html" class="wikilink1" title="jp:complexity">jp</a></div></li>  <li><div class="li"><a href="nl/complexity.html" class="wikilink2" title="nl:complexity" rel="nofollow">nl</a></div></li>  <li><div class="li"><a href="pl/complexity.html" class="wikilink1" title="pl:complexity">pl</a></div></li>  <li><div class="li"><a href="ro/complexity.html" class="wikilink2" title="ro:complexity" rel="nofollow">ro</a></div></li>  <li><div class="li"><a href="ru/complexity.html" class="wikilink2" title="ru:complexity" rel="nofollow">ru</a></div></li>  <li><div class="li"><a href="sk/complexity.html" class="wikilink2" title="sk:complexity" rel="nofollow">sk</a></div></li>  <li><div class="li"><a href="tr/complexity.html" class="wikilink2" title="tr:complexity" rel="nofollow">tr</a></div></li>  <li><div class="li"><a href="tw/complexity.html" class="wikilink2" title="tw:complexity" rel="nofollow">tw</a></div></li></ul></div>
   
   
  <div class="page">
    <script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-2828341-1";
urchinTracker();
</script>
    <!-- wikipage start -->
     
<h2><a name="time_complexity" id="time_complexity">Time Complexity</a></h2>
<div class="level2">
<p>
There are different measurements of the speed of any given algorithm. Given an
input size of N, they can be described as follows:
</p>
<table class="inline">
        <tr class="row0">
                <th class="col0">Name</th><th class="col1">Speed</th><th class="col2">Description</th><th class="col3">Formula</th><th class="col4">Example</th>
        </tr>
        <tr class="row1">
                <td class="col0">factorial time</td><td class="col1">slower</td><td class="col2">takes an amount of time proportional to N raised to the Nth power</td><td class="col3 centeralign">  N!  </td><td class="col4">Brute force solution to Traveling Salesman Problem</td>
        </tr>
        <tr class="row2">
                <td class="col0">exponential time</td><td class="col1">slow</td><td class="col2">takes an amount of time proportional to a constant raised to the Nth power</td><td class="col3 centeralign">  K<sup>N</sup>  </td><td class="col4">Brute force solution to Rubik&#039;s Cube</td>
        </tr>
        <tr class="row3">
                <td class="col0">polynomial time</td><td class="col1">fast</td><td class="col2">takes an amount of time proportional to N raised to some constant power</td><td class="col3 centeralign">  N<sup>K</sup>  </td><td class="col4">Comparison sorts (bubble, insertion, selection sort)</td>
        </tr>
        <tr class="row4">
                <td class="col0">linearithmic time</td><td class="col1">faster</td><td class="col2">takes an amount of time between linear and polynomial</td><td class="col3 centeralign">  N * log(N)  </td><td class="col4">The Linear logarithmic sorts (quicksort, heapsort, mergesort)</td>
        </tr>
        <tr class="row5">
                <td class="col0">linear time</td><td class="col1">even faster</td><td class="col2">takes an amount of time directly proportional to N</td><td class="col3 centeralign">  K * N  </td><td class="col4">Iterating through an array</td>
        </tr>
        <tr class="row6">
                <td class="col0">logarithmic time</td><td class="col1">much faster</td><td class="col2">takes an amount of time proportional to the logarithm of N</td><td class="col3 centeralign">  K * log(N)  </td><td class="col4">Binary Search</td>
        </tr>
        <tr class="row7">
                <td class="col0">constant time</td><td class="col1">fastest</td><td class="col2">takes a fixed amount of time, no matter how large the input is</td><td class="col3 centeralign">  K  </td><td class="col4">Array index lookup</td>
        </tr>
</table>
</div>
<div class="secedit"><form class="button btn_secedit" method="post" action="/wiki/complexity"><div class="no"><input type="hidden" name="do" value="edit" /><input type="hidden" name="lines" value="1-1171" /><input type="hidden" name="rev" value="1268650136" /><input type="submit" value="Edit" class="button" title="Time Complexity" /></div></form></div>
<h3><a name="complexity_analysis" id="complexity_analysis">Complexity Analysis</a></h3>
<div class="level3">
<p>
A given operation can have different time complexities with different orders/sets of input.  The different methods of time complexity analysis are as follows:
</p>
<table class="inline">
        <tr class="row0">
                <th class="col0">Name</th><th class="col1">Description</th><th class="col2">Example</th>
        </tr>
        <tr class="row1">
                <td class="col0">best-case</td><td class="col1">A case where the operation executes as fast as it possibly can</td><td class="col2"> Bubblesort has a best-case time complexity of N.</td>
        </tr>
        <tr class="row2">
                <td class="col0">average-case</td><td class="col1">A case where the operation executes in a time comparable to the majority of possible cases</td><td class="col2"> Quicksort has an average-case time complexity of N * log(N)</td>
        </tr>
        <tr class="row3">
                <td class="col0">worst-case</td><td class="col1">A case where the operation executes as slowly as it possibly can</td><td class="col2"> Quicksort has a worst-case time complexity of N<sup>2</sup></td>
        </tr>
        <tr class="row4">
                <td class="col0">amortized worst-case</td><td class="col1">The average worst-case taken over an infinite number of inputs</td><td class="col2"> vector::push_back() has an amortized worst-case time complexity of K (constant time)</td>
        </tr>
</table>
<p>
Choosing the right algorithm depends upon which cases you expect your application to encounter.  For example, an application that must protect itself from malicious input will avoid naive implementations of quicksort, which has a worst-case time complexity of N<sup>2</sup> despite having one of the fastest average-case time complexities compared to all other sorts.
</p>
</div>
<div class="secedit"><form class="button btn_secedit" method="post" action="/wiki/complexity"><div class="no"><input type="hidden" name="do" value="edit" /><input type="hidden" name="lines" value="1172-" /><input type="hidden" name="rev" value="1268650136" /><input type="submit" value="Edit" class="button" title="Complexity Analysis" /></div></form></div>
    <!-- wikipage stop -->
  </div>
  <div class="clearer">&nbsp;</div>
   
  <div class="stylefoot">
    <div class="meta">
      <div class="user">
              </div>
      <!--
      <div class="doc">
        complexity.txt &middot; Last modified: 03/15/2010 03:48 by 202.32.8.238      </div>
      -->
    </div>
    
    <div class="bar" id="bar__bottom">
      <div class="bar-left" id="bar__bottomleft">
        <a href="complexity.html"  class="action edit" accesskey="e" rel="nofollow">Edit this page</a> &#149;
        <a href="complexity.html"  class="action revisions" accesskey="o" rel="nofollow">Old revisions</a>      </div>
      <div class="bar-right" id="bar__bottomright">
         &#149;
         &#149;
         &#149;
        <a href="complexity.html"  class="action login" rel="nofollow">Login</a> &#149;
        <a href="complexity.html"  class="action index" accesskey="x" rel="nofollow">Index</a> &#149;
        <a href="complexity.html"  class="action recent" accesskey="r" rel="nofollow">Recent changes</a> &#149;
        <a  href="feed.php.html" title="Recent changes RSS feed">RSS</a> &#149;
        <a href='http://creativecommons.org/licenses/by/3.0/us/' title='Creative Commons license'>cc</a> &#149;
        <form action="/wiki/" accept-charset="utf-8" class="search" id="dw__search"><div class="no"><input type="hidden" name="do" value="search" /><input type="text" id="qsearch__in" accesskey="f" name="id" class="edit" title="[ALT+F]" /><input type="submit" value="Search" class="button" title="Search" /><div id="qsearch__out" class="ajax_qsearch JSpopup"></div></div></form>&nbsp;
      </div>
      <div class="clearer"></div>
    </div>
  </div>
</div>
<div class="no"><img src="/wiki/lib/exe/indexer.php?id=complexity&amp;1273197003" width="1" height="1" alt=""  /></div>
</body>
</html>