Maps and Sets Study Guide - Revision history

Admin: Fix typos, improve definition accuracy, fill empty OOP Principles section, fix geometric series formula (via update-page on MediaWiki MCP Server)

2026-06-08T03:59:01Z

Fix typos, improve definition accuracy, fill empty OOP Principles section, fix geometric series formula (via update-page on MediaWiki MCP Server)

2017-07-11T07:02:53Z

Algorithms for Operations

← Older revision		Revision as of 07:02, 11 July 2017
Line 226:		Line 226:
	* use protected getPredecessor method		* use protected getPredecessor method
	* find predecessor of node to be removed		* find predecessor of node to be removed
	* predecessor.getNext(using ~~leel~~ from prior step), gives result node		* predecessor.getNext(using level from prior step), gives result node

	remove step 2:		remove step 2:

2017-07-11T07:02:35Z

Algorithms for Operations

← Older revision		Revision as of 07:02, 11 July 2017
Line 193:		Line 193:

	Hash Maps:		Hash Maps:
	* All operations are covered by [[Hash ~~Table~~ Study Guide]] operations section		* All operations are covered by [[Hash Tables Study Guide]] operations section

	Tree Maps:		Tree Maps:

2017-07-11T07:01:58Z

Big O Complexity

← Older revision		Revision as of 07:01, 11 July 2017
Line 295:		Line 295:
	\|-		\|-
	\|find lt/find lte/find gt/find gte		\|find lt/find lte/find gt/find gte
	\|O(log n)		\|O(log N)

	\|-		\|-
	\|find range		\|find range
	\|O(log n + s)		\|O(log N + S), S items returned

	\|-		\|-
	\|iterate over all items		\|iterate over all items
	\|O(n)		\|O(N)

	\|}		\|}

2017-07-11T07:01:34Z

Big O Complexity

@@ Line 274: / Line 274: @@
 |-
-|sett
+|set
 |O(log N)
@@ Line 284: / Line 284: @@
 |remove
 |O(log N)
 |}

2017-07-11T07:00:06Z

Probabilistic Analysis of Performance

2017-07-11T06:59:50Z

Space Usage

← Older revision		Revision as of 06:59, 11 July 2017
Line 286:		Line 286:

	\|}		\|}

			===Probabilistic Analysis of Performance===

			Performance analysis:
			* Base it on '''expectation'''
			* High likelihood of good performance, given by Chernoff bounds
			* Bounded height with high probability

			<math>
			P_i \leq \left( \dfrac{1}{2} \right)^i n
			</math>

			<math>
			P_i \leq \dfrac{n}{2^i}
			</math>

			at a given level i, what is the probability of having an entry? 1/2, from coin flip. These combine to give the expression above.

			Given a constant c > 1, the height of a tree is larger than c log n with probability of '''at most'''

			<math>
			\dfrac{1}{n^{c-1}}
			</math>

			The probability that the height is smaller than c log n is

			<math>
			\left( 1 - \dfrac{1}{n^{c-1}}
			</math>


	===Space Usage===		===Space Usage===

2017-07-11T06:56:52Z

Space Usage

2017-07-11T06:56:04Z

Big O Complexity Table

← Older revision		Revision as of 06:56, 11 July 2017
Line 256:		Line 256:
	==Big O Complexity Table==		==Big O Complexity Table==

	Complexity depends on implementation. See [[Hash ~~Table~~ Study Guide]] and [[Search Trees Study Guide]] for big O tables.		Complexity depends on implementation. See [[Hash Tables Study Guide]] and [[Search Trees Study Guide]] for big O tables.

	==Analysis of Skip Lists==		==Analysis of Skip Lists==

2017-07-11T06:55:49Z

Complexity and Cost

← Older revision		Revision as of 06:55, 11 July 2017
Line 253:		Line 253:

	=Complexity and Cost=		=Complexity and Cost=

			==Big O Complexity Table==

			Complexity depends on implementation. See [[Hash Table Study Guide]] and [[Search Trees Study Guide]] for big O tables.

			==Analysis of Skip Lists==

			===Big O Complexity===

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Skip Lists
			\|-
			\|
			\|<br /><br />
			Skip List

			\|-
			\|get
			\|O(log N)

			\|-
			\|sett
			\|O(log N)

			\|-
			\|contains
			\|O(log N)

			\|-
			\|remove
			\|O(log N)

			\|}

			===Space Usage===

			We can analyze the space usage of a probabilistic data set by analyzing the expected sum of number of nodes. This is given by the sum of number of positions at level i:

			<math>
			\sum_{i=0}^{h} n \mathbb{P}_i = n \left( \sum_{i=0}^{h} \dfrac{1}{2^i} \right)
			</math>

			The last term can be simplified using the fact that

			<math>
			\sum_{i=1}^{n} a^i = \dfrac{a^{i+1} - 1}{a-1}
			</math>

			to say that

			<math>
			\sum_{i=0}^{h} \dfrac{1}{2^i} = 2 \left( 1 - \dfrac{1}{2^{h+1}} \right)
			</math>

			This number is bounded by 2, and therefore

			<math>
			\mathbb{E}(N) = n \mathbb{P} = \sum_{i=0}^{h} n \mathbb{P}_i \leq 2n
			</math>

			and therefore the expected number of nodes in the skip list is O(n):

			<math>
			\mathbb{E}(N) \sim O(n)
			<math>

	=OOP Principles=		=OOP Principles=