codeblocks-ep/help/html/programmerHelp/cppreference.com/complexity.html at master · maifeeulasad/codeblocks-ep · GitHub

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
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>

<!-- Mirrored from cppreference.com/complexity.html by HTTrack Website Copier/3.x [XR&CO'2004], Tue, 22 Jan 2008 06:25:35 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=iso-8859-1"><!-- /Added by HTTrack -->
<head>
  <meta name="generator" content=
  "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org">

  <title>Complexity</title>
  <link href="cppreference.css" rel="stylesheet" type="text/css">
  <link href="prettify.css" type="text/css" rel="stylesheet" />
  <script type="text/javascript" src="prettify.js"></script>
</head>

<body onload="prettyPrint()">
<table>
  <tr>
  <td>
  <div class="body-content">

  <div class="header-box">
    <a href="index-2.html">cppreference.com</a> &gt; Complexity
  </div>

  <h3>Complexity</h3>

  <p>There are different measurements of the speed of any given
  algorithm. Given an input size of <strong>N</strong>, they can be
  described as follows:</p>

  <table class="misc-table">
    <tr>
      <th>Name</th>

      <th>Speed</th>

      <th>Description</th>

      <th>Formula</th>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">exponential time</td>

      <td class="misc-table-td">slow</td>

      <td class="misc-table-td">takes an amount of time proportional to a constant raised to
      the <strong>N</strong>th power</td>

      <td class="misc-table-td">K^<strong>N</strong></td>
    </tr>

    <tr class="misc-table-tr-1">
      <td class="misc-table-td">polynomial time</td>

      <td class="misc-table-td">fast</td>

      <td class="misc-table-td">takes an amount of time proportional to <strong>N</strong>
      raised to some constant power</td>

      <td class="misc-table-td"><strong>N</strong>^K</td>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">linear time</td>

      <td class="misc-table-td">faster</td>

      <td class="misc-table-td">takes an amount of time directly proportional to
      <strong>N</strong></td>

      <td class="misc-table-td">K * <strong>N</strong></td>
    </tr>

    <tr class="misc-table-tr-1">
      <td class="misc-table-td">logarithmic time</td>

      <td class="misc-table-td">much faster</td>

      <td class="misc-table-td">takes an amount of time proportional to the logarithm of
      <strong>N</strong></td>

      <td class="misc-table-td">K * log(<strong>N</strong>)</td>
    </tr>

    <tr class="misc-table-tr-2">
      <td class="misc-table-td">constant time</td>

      <td class="misc-table-td">fastest</td>

      <td class="misc-table-td">takes a fixed amount of time, no matter how large the input
      is</td>

      <td class="misc-table-td">K</td>
    </tr>
  </table>
  </div>
  </td>


<script src="../www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-2828341-1";
urchinTracker();
</script>
  </tr>
  </table>
</body>
<!-- Mirrored from cppreference.com/complexity.html by HTTrack Website Copier/3.x [XR&CO'2004], Tue, 22 Jan 2008 06:25:35 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=iso-8859-1"><!-- /Added by HTTrack -->
</html>