WGU C949 - Big O Notation FREQUENTLY TESTED QUESTIONS WITH CORRECT ANSWERS | BRAND NEW!
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/29
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai | Chat |
|---|
No analytics yet
Send a link to your students to track their progress
30 Terms
O(1) - Constant Time
Definition: The algorithm takes the same amount of time regardless of the input size.
Characteristics: No loops or recursion, only a few basic operations.
Spotting in Pseudocode: Look for code that performs a fixed number of operations, regardless of input size.
O(1) - Constant Time
O(log n) - Logarithmic Time
Definition: The algorithm reduces the problem size by a constant factor each step.
Characteristics: Typically involves divide-and-conquer or binary search.
Spotting in Pseudocode: Look for algorithms that repeatedly halve the problem size, such as binary search.
O(log n) - Logarithmic Time
O(n) - Linear Time
Definition: The algorithm's running time increases linearly with the input size.
Characteristics: Single loops that iterate through all elements.
Spotting in Pseudocode: Look for single loops that iterate through the entire input.
Algorithms with this Complexity: Bucket, Radix
O(n) - Linear Time
O(n log n) - Linearithmic Time
Definition: The algorithm involves a combination of linear and logarithmic time.
Characteristics: Often found in efficient sorting algorithms like merge sort and quicksort.
Spotting in Pseudocode: Look for divide-and-conquer algorithms that split the input into smaller parts, solve them recursively, and merge the results.
Algorithms with this Complexity: Quicksort, Heapsort, Mergesort
O(n log n) - Linearithmic Time
O(n^2) - Quadratic Time
Definition: The algorithm's running time is proportional to the square of the input size.
Characteristics: Typically involves nested loops, each iterating through the input.
Spotting in Pseudocode: Look for nested loops where each loop iterates through the input.
Algorithms with this Complexity: Bubble, Selection, Insertion
O(n^2) - Quadratic Time
O(2n) - Exponential Time
Definition: The algorithm's running time doubles with each additional element in the input.
Characteristics: Commonly found in recursive algorithms that solve problems by solving all subproblems.
Spotting in Pseudocode: Look for recursive algorithms where the problem size decreases by a small amount in each recursive call, and there are multiple recursive calls.
O(2n) - Exponential Time
O(n!) - Factorial Time
Definition: The algorithm's running time is proportional to the factorial of the input size.
Characteristics: Often found in algorithms that generate all permutations of the input.
Spotting in Pseudocode: Look for algorithms that involve generating all possible permutations or combinations of the input.
O(n!) - Factorial Time
Bubble Sort
The simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
Average/Typical: O(n^2)
Big-O/Worse: O(n^2)
Selection Sort
A simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
Average/Typical: O(n^2)
Big-O/Worse: O(n^2)
Insertion Sort
A simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list.
Average/Typical: O(n^2)
Big-O/Worse: O(n^2)
Quicksort
A sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.
Average/Typical: O(n log n)
Big-O/Worse: O(n^2)
Bucket Sort
A sorting technique that involves dividing elements into various groups, or buckets.
Average/Typical: O(n)
Big-O/Worse: O(n^2)
Heapsort
A comparison-based sorting technique based on Binary Heap data structure.
Average/Typical: O(n log n)
Big-O/Worse: O(n log n)
Mergesort
A sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.
Average/Typical: O(n log n)
Big-O/Worse: O(n log n)
Radix Sort
A linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys.
Average/Typical: O(n)
Big-O/Worse: O(n)
Bubble Sort
Selection Sort
Insertion Sort
Quicksort
Bucket Sort
Heapsort
Mergesort
Radix Sort
