Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Branch: master
389 lines (385 sloc) 16.092 kB
<h2 id="data-structures">Data Structure Operations</h2>
<table class="table table-bordered table-striped">
<thead>
<tr>
<th>Data Structure</th>
<th colspan="8">Time Complexity</th>
<th>Space Complexity</th>
</tr>
<tr>
<th></th>
<th colspan="4">Average</th>
<th colspan="4">Worst</th>
<th>Worst</th>
</tr>
<tr>
<th></th>
<th>Access</th>
<th>Search</th>
<th>Insertion</th>
<th>Deletion</th>
<th>Access</th>
<th>Search</th>
<th>Insertion</th>
<th>Deletion</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Array_data_structure">Array</a></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Stack_(abstract_data_type)">Stack</a></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists">Singly-Linked List</a></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Doubly_linked_list">Doubly-Linked List</a></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Skip_list">Skip List</a></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="orange">O(n log(n))</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Hash_table">Hash Table</a></td>
<td><code>-</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code>-</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Binary_search_tree">Binary Search Tree</a></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="https://en.wikipedia.org/wiki/Cartesian_tree">Cartesian Tree</a></td>
<td><code>-</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code>-</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/B_tree">B-Tree</a></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Red-black_tree">Red-Black Tree</a></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="https://en.wikipedia.org/wiki/Splay_tree">Splay Tree</a></td>
<td><code>-</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code>-</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/AVL_tree">AVL Tree</a></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
</tbody>
</table>
<h2 id="sorting">Array Sorting Algorithms</h2>
<table class="table table-bordered table-striped">
<thead>
<tr>
<th>Algorithm</th>
<th colspan="3">Time Complexity</th>
<th>Space Complexity</th>
</tr>
<tr>
<th></th>
<th>Best</th>
<th>Average</th>
<th>Worst</th>
<th>Worst</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Merge_sort">Mergesort</a></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Timsort">Timsort</a></td>
<td><code class="green">O(n)</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Heapsort">Heapsort</a></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="orange">O(n log(n))</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Bubble_sort">Bubble Sort</a></td>
<td><code class="green">O(n)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Insertion_sort">Insertion Sort</a></td>
<td><code class="green">O(n)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Selection_sort">Selection Sort</a></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Shellsort">Shell Sort</a></td>
<td><code class="green">O(n)</code></td>
<td><code class="red">O((nlog(n))^2)</code></td>
<td><code class="red">O((nlog(n))^2)</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a rel="tooltip" title="Only for integers. k is a number of buckets" href="http://en.wikipedia.org/wiki/Bucket_sort">Bucket Sort</a></td>
<td><code class="green">O(n+k)</code></td>
<td><code class="green">O(n+k)</code></td>
<td><code class="red">O(n^2)</code></td>
<td><code class="yellow">O(n)</code></td>
</tr>
<tr>
<td><a rel="tooltip" title="Constant number of digits 'k'" href="http://en.wikipedia.org/wiki/Radix_sort">Radix Sort</a></td>
<td><code class="green">O(nk)</code></td>
<td><code class="green">O(nk)</code></td>
<td><code class="green">O(nk)</code></td>
<td><code class="yellow">O(n+k)</code></td>
</tr>
</tbody>
</table>
<h2 id="graphs">Graph Operations</h2>
<table class="table table-bordered table-striped">
<tbody>
<tr>
<th>Node / Edge Management</th>
<th>Storage</th>
<th>Add Vertex</th>
<th>Add Edge</th>
<th>Remove Vertex</th>
<th>Remove Edge</th>
<th>Query</th>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Adjacency_list">Adjacency list</a></td>
<td><code class="yellow">O(|V|+|E|)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(|V| + |E|)</code></td>
<td><code class="yellow">O(|E|)</code></td>
<td><code class="yellow">O(|V|)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Incidence_list">Incidence list</a></td>
<td><code class="yellow">O(|V|+|E|)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow">O(|E|)</code></td>
<td><code class="yellow">O(|E|)</code></td>
<td><code class="yellow">O(|E|)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Adjacency_matrix">Adjacency matrix</a></td>
<td><code class="red">O(|V|^2)</code></td>
<td><code class="red">O(|V|^2)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="red">O(|V|^2)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Incidence_matrix">Incidence matrix</a></td>
<td><code class="red">O(|V| &sdot; |E|)</code></td>
<td><code class="red">O(|V| &sdot; |E|)</code></td>
<td><code class="red">O(|V| &sdot; |E|)</code></td>
<td><code class="red">O(|V| &sdot; |E|)</code></td>
<td><code class="red">O(|V| &sdot; |E|)</code></td>
<td><code class="yellow">O(|E|)</code></td>
</tr>
</tbody>
</table>
<h2 id="heaps">Heap Operations</h2>
<table class="table table-bordered table-striped">
<thead>
<tr>
<th>Type</th>
<th colspan="7">Time Complexity</th>
</tr>
<tr>
<th></th>
<th>Heapify</th>
<th>Find Max</th>
<th>Extract Max</th>
<th>Increase Key</th>
<th>Insert</th>
<th>Delete</th>
<th>Merge</th>
<th></th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Linked_list">Linked List (sorted)</a></td>
<td><code>-</code></td> <!-- heapify -->
<td><code class="green">O(1)</code></td> <!-- Find max -->
<td><code class="green">O(1)</code></td> <!-- Extract max -->
<td><code class="red">O(n)</code></td> <!-- Increase -->
<td><code class="red">O(n)</code></td> <!-- insert -->
<td><code class="green">O(1)</code></td> <!-- delete -->
<td><code class="red">O(m+n)</code></td> <!-- merge -->
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Linked_list">Linked List (unsorted)</a></td>
<td><code>-</code></td> <!-- heapify -->
<td><code class="red">O(n)</code></td> <!-- Find max -->
<td><code class="red">O(n)</code></td> <!-- Extract max -->
<td><code class="green">O(1)</code></td> <!-- Increase -->
<td><code class="green">O(1)</code></td> <!-- insert -->
<td><code class="green">O(1)</code></td> <!-- delete -->
<td><code class="green">O(1)</code></td> <!-- merge -->
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Binary_heap">Binary Heap</a></td>
<td><code class="yellow">O(n)</code></td>
<td><code class="green">O(1)</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="red">O(m+n)</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Binomial_heap">Binomial Heap</a></td>
<td><code>-</code></td>
<td><code rel="tooltip" title="With aux pointer" class="green">O(1)</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code rel="tooltip" title="Amortized" class="green">O(1)</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
<td><code class="yellow-green">O(log(n))</code></td>
</tr>
<tr>
<td><a href="http://en.wikipedia.org/wiki/Fibonacci_heap">Fibonacci Heap</a></td>
<td><code>-</code></td>
<td><code class="green">O(1)</code></td>
<td><code rel="tooltip" title="Amortized" class="yellow-green">O(log(n))</code></td>
<td><code rel="tooltip" title="Amortized" class="green">O(1)</code></td>
<td><code class="green">O(1)</code></td>
<td><code rel="tooltip" title="Amortized" class="yellow-green">O(log(n))</code></td>
<td><code class="green">O(1)</code></td>
</tr>
</tbody>
</table>
Jump to Line
Something went wrong with that request. Please try again.