Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
31 Cards in this Set
- Front
- Back
|
Adding a new node to a linked list
|
O(1)
|
|
|
Deleting the front node from a linked list
|
O(1)
|
|
|
Removing the last node of an array
|
O(1)
|
|
|
Adding a new node to the end of a linked list with a rear pointer to the last node
|
O(1)
|
|
|
What is O(1)?
|
O(1) is the time complexity of an algorithm that operates in constant time. The process time required stays constant regardless of the data size.
|
|
|
What is O(n)?
|
O(n) is the time complexity of an algorithm that operates in linear time. The process time changes in the same ratio as the data size.
|
|
|
Linear search
|
O(n)
|
|
|
Displaying elements in a one-dimensional array
|
O(n)
|
|
|
Traversing a linked list
|
O(n)
|
|
|
Traversing a binary tree
|
O(n)
|
|
|
Smart Bubble Sort with a sorted list
|
O(n)
|
|
|
What is O(log n)?
|
O(log n) is the time complexity of an algorithm that operates in logarithmic time. Occurs in most cases when program statements demonstrate a process that divides the workload in half at each iteration through the algorithm.
|
|
|
Binary Search of a sorted array
|
O(log n)
|
|
|
Binary Search of a Binary Search Tree (fairly balanced)
|
O(log n)
|
|
|
Inserting a new node in a Binary Search Tree
|
O(log n)
|
|
|
Number of merges performed in a Merge Sort
|
O(log n)
|
|
|
What is O(n²)?
|
O(n²) is the time complexity of an algorithm that operates in quadratic time. Occurs in most cases when nested loops process data.
|
|
|
Bubble Sort
|
O(n²)
|
|
|
Selection Sort
|
O(n²)
|
|
|
Insertion Sort
|
O(n²)
|
|
|
What is O(n³)?
|
n³ is the time complexity of an algorithm that operates in cubic time. Occurs in most cases when triple nested loops process data.
|
|
|
Matrix Multiplication
|
O(n³)
|
|
|
3D graphics algorithms
|
O(n³)
|
|
|
What is O(n log n)?
|
O(n log n) is the time complexity of an algorithm that operates in n times logarithmic time.
|
|
|
Merge Sort
|
O(n log n)
|
|
|
Binary Tree Sort
|
O(n log n)
|
|
|
Quick Sort
|
O(n log n)
|
|
|
Heap Sort
|
O(n log n)
|
|
|
What is O(2^n)?
|
O(2^n) is the time complexity of an algorithm that operates in exponential time. This means that process times doubles with the addition of each data element.
|
|
|
Recursive Fibonacci Sequence method
|
O(2^n)
|
|
|
Tower of Hanoi solution
|
O(2^n)
|
