Summary
Summary Datastructures Overview
- Course
- Institution
This is a great overview of the course Data Structures. All algorithms and data structures are managed in a nice overview. Also other important things for the course.
[Show more]
Seller
Followroyvandijk06
Content preview
Algorithms Running time Features----- Sorting Algorithms -----
Name: QuickSort Worst Case: Θ(n2) (Θ(n log n) using linear time Using Pivot: yes
median finding) Stable: Yes
Average Case: Θ(n log n) In Place: Yes
Name: MergeSort Worst Case: O(n log n) Stable: Yes
In Place: No
Name: HeapSort Worst Case: O(n log n) Stable: No
In Place: Yes
Name: BubbleSort Worst Case: O(n2)
Name: InsertionSort Worst Case: Θ(n2) Stable: Yes
In place: Yes
Name: SelectionSort Worst Case: O(n2)
Name: BucketSort Worst Case: O(n2)
Input: Array with real number elements between 0 Average Case: Θ(n)
and 1 Best Case: Θ(n)
Name: RadixSort Worst Case: O(nk)
Input: Array with integer elements of d digits Average Case: Θ(d(n+k))
Best Case: Θ(n)
Name: CountingSort Worst Case: Θ(n) Stable: Yes
Input: Array with interger elements in the range 0 to k Avarage Case: Θ(n+k)
Name: TopologicalSort Worst Case: Θ(V + E)
Input: Directed, acyclic graph (DAG) G = (V, E)
Output: A linear ordering of v1 ,v2 ,…, vn ∈ V, such that
if (vi ,vj ) ∈ E then i < j
----- Searching Algorithms -----
Name: LinearSearch Worst Case: Θ(n)
Input: Increasing sequence of n numbers A = ‹a1, a2, Average Case: Θ(n/2) (if successful)
…, an› and value v Best Case: Θ(1)
Output: An index i such that A[i] = v or NIL if v not in A
Name: BinarySearch Worst Case: Θ(log n)
Input: Increasing sequence of n numbers A = ‹a1, a2, Average Case: Θ(log n)
…, an› and value v Best Case: Θ(log n)
Output: an index i such that A[i] = v or NIL if v not in A
Name: Chained-Hash-Search Worst Case: O(1 + length of T[h(k)]) = O(n)
Input: List T and a key k Average Case: O(1 + # elements in T[h(k)]
Output: Element with key k in list T[h(k)] ahead of k) = Θ(1+α) (Θ(1) if m = Ω(n))
Name: TreeSearch Worst Case: Θ(h)
Average Case: Θ(length of search path)
Name: BreadthFirstSearch or BFS Worst Case: O(V + E)
Name: DepthFirstSearch or DFS Worst Case: Θ(V + E)
----- Other Algorithms -----
Name: Krustal or Prim Worst Case: O(E log V)
Input: undirected, weighted graph G = (V, E)
weighted graph = each edge (u, v) has a weight w(u, v)
Output: a set of edges T ⊂ E such that 1. T connects all
vertices, and 2. w(T) = ∑ (u, v) ∈ T w(u,v) is minimized
Operations Search Insert Delete Max- Extract- Increase- Max- Build- Heap-
Datastructures imum Max Key Heapify Max-Heap sort
Sorted List Θ(n) Θ(n) Θ(1) Θ(1) Θ(1) Θ(n)
Sorted Array Θ(log n) Θ(n) Θ(n) Θ(1) Θ(n) Θ(n)
Heap Θ(log n) Θ(log n) Θ(1) Θ(log n) Θ(log n) Θ(log n) Θ(n) Θ(nlog n)
Tree (BST or R-B-Tree) Θ(log n) Θ(log n) Θ(log n) Θ(log n)
Hash Table Θ(1) Θ(1) Θ(1)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller royvandijk06. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.05. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78861 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now