CIS 3020 Part 5 - Revision history

Jka: /* Growth of Complexity Functions */

2007-04-02T15:23:05Z

Growth of Complexity Functions

2007-04-02T15:22:15Z

Important Order Relationships

2007-04-02T15:14:40Z

Algebraic Identities for Big-O

2007-04-02T15:10:42Z

Algebraic Identities for Big-O

2007-04-02T15:09:35Z

Algebraic Identities for Big-O

2007-04-02T15:08:47Z

Algebraic Identities for Big-O

2007-04-02T15:08:22Z

Algebraic Identities for Big-O

2007-04-02T15:04:58Z

Algebraic Identities for Big-O

2007-04-02T15:04:42Z

Algebraic Identities for Big-O

2007-04-02T15:01:59Z

Algebraic Identities for Big-O

← Older revision		Revision as of 15:23, 2 April 2007
Line 276:		Line 276:
	# Approximately the number of machine instructions executed on a 1 gigaflop (10<sup>9</sup>) supercomputer in 5000 years.		# Approximately the number of machine instructions executed on a 1 gigaflop (10<sup>9</sup>) supercomputer in 5000 years.
	# Approximately 500 billion times the age of the universe (in nanoseconds: 10<sup>-9</sup>)		# Approximately 500 billion times the age of the universe (in nanoseconds: 10<sup>-9</sup>)
		+	==[[CIS 3020 Part 6]]==

← Older revision		Revision as of 15:22, 2 April 2007
Line 247:		Line 247:
	\| log(n) \|\| dominates 1		\| log(n) \|\| dominates 1
	\|}		\|}
		+	==Special Big-O Complexities==
		+	* A complexity of O(1) is called ''Constant Complexity''
		+	* A complexity of O(N) is called ''Linear Complexity''
		+	* A complexity of O(N<sup>K</sup>) is called ''Polynomial Complexity''
		+	* Any complexity dominating O(2<sup>N</sup>) is called ''Exponential Complexity''
		+	==Growth of Complexity Functions==
		+	{\| border="1"
		+	! log(n) !! n !! n * log(n) !! n<sup>2</sup> !! n<sup>3</sup> !! 2<sup>n</sup>
		+	\|-
		+	\| 0 \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 2
		+	\|-
		+	\| 1 \|\| 2 \|\| 2 \|\| 4 \|\| 8 \|\| 4
		+	\|-
		+	\| 2 \|\| 4 \|\| 8 \|\| 16 \|\| 64 \|\| 16
		+	\|-
		+	\| 3 \|\| 8 \|\| 24 \|\| 64 \|\| 512 \|\| 256
		+	\|-
		+	\| 4 \|\| 16 \|\| 64 \|\| 256 \|\| 4096 \|\| 65536
		+	\|-
		+	\| 5 \|\| 32 \|\| 160 \|\| 1024 \|\| 32768 \|\| 4294967296
		+	\|-
		+	\| 6 \|\| 64 \|\| 384 \|\| 4096 \|\| 262144 \|\| (Note 1)
		+	\|-
		+	\| 7 \|\| 128 \|\| 896 \|\| 16384 \|\| 2097152 \|\| (Note 2)
		+	\|-
		+	\| 8 \|\| 256 \|\| 2048 \|\| 65536 \|\| 16777216 \|\| ?????
		+	\|}
		+	# Approximately the number of machine instructions executed on a 1 gigaflop (10<sup>9</sup>) supercomputer in 5000 years.
		+	# Approximately 500 billion times the age of the universe (in nanoseconds: 10<sup>-9</sup>)

← Older revision		Revision as of 15:14, 2 April 2007
Line 225:		Line 225:
	</ol>		</ol>
	: <code>n<sup>3</sup>m² = O(n<sup>3</sup>) * O(m²)</code>		: <code>n<sup>3</sup>m² = O(n<sup>3</sup>) * O(m²)</code>
		+	==Important Order Relationships==
		+	for the following assume that k and c are positive constants and that n is a variable
		+	{\| border = "1"
		+	\|-
		+	\| n<sup>n</sup> \|\| dominates n!
		+	\|-
		+	\| n! \|\| dominates c<sup>n</sup>
		+	\|-
		+	\| c<sup>n</sup> \|\| dominates k<sup>n</sup>, so long as c>k
		+	\|-
		+	\| k<sup>n</sup> \|\| dominates k<sup>c</sup>, so long as k>1
		+	\|-
		+	\| n<sup>c</sup> \|\| dominates n<sup>k</sup>, so long as c>k
		+	\|-
		+	\| n<sup>2</sup> \|\| dominates n * log(n)
		+	\|-
		+	\| n * log(n) \|\| dominates n
		+	\|-
		+	\| n \|\| dominates log(n)
		+	\|-
		+	\| log(n) \|\| dominates 1
		+	\|}

@@ Line 210: / Line 210: @@
 # c * f = O(f) -- you can drop constant multipliers
-<pre>
+: <code>17n = O(n)</code>
-n² = O(n²)
+: <code>25n² = O(n²)</code>
-= O(1)
+: <code>99 = O(1)</code>
 <ol start="2">
 <li>f + g = O(f), so long as f dominates g
 </ol>
-: n² + 3 = O(n²)
+: <code>n² + 3 = O(n²)</code>
-: n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)
+: <code>n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)</code>
 <ol start="3">
 <li>f * g = O(f) * O(g)
 </ol>
-<pre>
+: <code>n<sup>3</sup>m² = O(n<sup>3</sup>) * O(m²)</code>

@@ Line 220: / Line 220: @@
 <li>f + g = O(f), so long as f dominates g
 </ol>
-<code>
+: n² + 3 = O(n²)
-n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)
+: n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)
 <ol start="3">
 <li>f * g = O(f) * O(g)

@@ Line 217: / Line 217: @@
 = O(1)
 </pre>
-#: f + g = O(f), so long as f dominates g
+<ol start="2">

@@ Line 209: / Line 209: @@
 Assume c denotes a constant and that f and g are arbitrary functions
-# c * f = O(f) -- you can drop constant multipliers<pre>
+# c * f = O(f) -- you can drop constant multipliers
 n = O(n)