Big O Notation
Quiz yourself by thinking what should be in
each of the black spaces below before clicking
on it to display the answer.
Help!
|
|
||||
|---|---|---|---|---|---|
| What is Binary Search? | An efficient algorithm for finding an item in an ordered list of items. It works by repeatedly divide the list in half to narrow down the possible locations of the item.
🗑
|
||||
| What is the opposite of Binary Search? | Linear Search
🗑
|
||||
| What is the opposite of Linear Search? | Binary Search
🗑
|
||||
| What is Linear Search? | A relatively inefficient algorithm for finding an item in a list. It works by examining each item in the list from the beginning to find the item you’re looking for.
🗑
|
||||
| Which is more efficient: binary or linear searches? | Binary, b/c with each step you narrow down the possibilities by 1/2. A linear search is less efficient b/c in the worst case scenario, you'd need to go through the whole array. It could take as many as n guesses, where n equals length of the array.
🗑
|
||||
| Each time you double the size of an array, how many more guesses would you need when conducting a binary search? | We need at most 1 more guess
🗑
|
||||
| If we need at most m guesses for an array of length n, then how many guesses will we need for an array of length 2n? Why? | We’d need at most m + 1 guesses, because each time you double the size of the array you need to account for one more guess.
🗑
|
||||
| What is Big O notation? | The way we analyze how efficient an algorithm is, specifically how much time it needs to run and how much space in memory it needs to run.
🗑
|
||||
| In Big O, we ignore the ___ parts of an algorithm and focus on the __ parts. | We ignore the little parts and focus on the big parts that have the most impact.
🗑
|
||||
| Given the algorithm 3x² + x + 1, what is time complexity? Why? | O(n²). We ignore the x, 1, and 3 because they do not affect the run time as much as the exponent.
🗑
|
||||
| What is the time complexity of O(n²) + O(n) or O(n² + n) ? Why? | n²
When an algorithm is a mix of orders, the dominant order is shown and the rest are dropped.
🗑
|
||||
| Why are constants dropped in Big O notation? | Because they only shift the graph slightly and don't affect the overall look of the graph.
O(2n) would be shortened to O(n)
O(1/2n) would be shortened to O(n)
🗑
|
||||
| What is the time complexity of an algorithm with one loop? Why? | O(n), because we go through all the inputs in the loop once.
🗑
|
||||
| In Big O notation, which scenarios are we most concerned with? | The worst case scenario
🗑
|
||||
| What is the time complexity of an algorithm with 2 nested loops? Is this an optimal algorithm? | O(n²), because for every input we have to go through a full loop inside of another loop. It's not optimal because the steps increase exponentially as the input increases.
🗑
|
||||
| What is quadratic time complexity? | O(n²)
🗑
|
||||
| What is the time complexity of an algorithm with 3 nested loops? Is this an optimal algorithm? | O(n³). It's not optimal because the steps increase exponentially as the input increases.
🗑
|
||||
| What is cubic time complexity? | O(n³)
🗑
|
||||
| What is the time complexity of an algorithm with no loops? | O(1), or constant time.
🗑
|
||||
| What is constant time complexity? | O(1)
An algorithm that is constant is independent of the size of the data set it's operating on (it doesn't rely on n). You can have as many elements as you want, but the number of steps in the algorithm won't change.
🗑
|
||||
| What is the time complexity of an algorithm that passes an array into a function and prints the first element of the array? | O(1) or constant, because regardless of the size of the array it will only print the first element.
🗑
|
||||
| What is logarithmic time? Is it efficient? | O(log(n))
The data set size affects the efficiency of an algorithm in a logarithmic fashion, meaning the time/steps increase as the size of the input increases, but it grows at a slow rate. Examples include binary search and (some) recursive algorithms.
🗑
|
||||
| What is the time complexity of an algorithm that uses binary search? | O(log(n)), or Logarithmic Time
🗑
|
||||
| If you search through a sorted phonebook for a specific name by halving the book to narrow down options until you find the name you're looking for, what would be the time complexity? | O(log(n)) or logarithmic time
🗑
|
||||
| If you search through a phonebook that's not sorted into alphabetical order, what would be the time complexity? | O(n), or linear time, because you would need to search through the entire book from the beginning to find the name you're looking for.
🗑
|
||||
| Every time you have to halve a data set until you find 1 or double a data set to find n, what is the time complexity? | O(log(n))
🗑
|
||||
| Describe linear time complexity. | O(n). The algorithm's performance is directly proportional to the size of the data set being processed. If the number of elements (n) increases, the number of steps will increase.
🗑
|
||||
| What is O(n) complexity. | Linear time complexity. The algorithm's performance is directly proportional to the size of the data set being processed. If the number of elements (n) in the set increases, the number of steps will increase as well.
🗑
|
||||
| What is the time complexity of passing an array into a function and printing each element? | O(n), or linear, because the run-time will depend on the number of items in the data set, or n.
🗑
|
||||
| What is the time complexity of the function: i = 0; while i < n do i = i+1 | O(n), or linear, because the run-time will depend on n, or the length of the data set.
🗑
|
||||
| What is factorial time complexity. Is it optimal for an algorithm? | O(n!). It's not optimal because the number of steps increases very quickly.
🗑
|
||||
| Why isn't o(n!) optimal? | The no. of steps increases quickly. If a traveling salesman needs to visit 3 towns and needs the shortest route to pass through each town once, complexity will be 3! w/ 3 unique possibilities. Add 1 more town and it becomes 4!, w/12 unique possibilities.
🗑
|
||||
| What is meant by Big O Notation for time? | Optimizing the algorithm to take less time to run.
🗑
|
||||
| What is meant by Big O Notation for space? | Optimizing the algorithm to use less memory.
🗑
|
||||
| Describe is O(1) space complexity. | When a new variable is not assigned. For example:
while n >= 0, puts “Hi”, n += 1
🗑
|
||||
| Describe O(n) space complexity. | When your array scales based on the input when you run it. For example:
When you take in a number, create an array the size of the input, and loop through it n number of times.
🗑
|
||||
| Describe Array data structure or (native) arrays or arrays in strongly typed languages? | Native arrays are homogenous, meaning all elements are of the same type (integer array, character array), allocated in a contiguous block of memory., and static data, meaning once created, the size of an array is fixed and you can't add more items.
🗑
|
||||
| How are objects of Ruby’s Array class different from native arrays? | Ruby arrays can contain different elements (can have integers, strings, symbols together) b/c all elements in a Ruby array are object references, make . no claims about where objects in the array are stored in memory, and you can resize them.
🗑
|
||||
| Why do computers save information in binary? | Binary can precisely represent information using a high voltage (1) and low voltage (0). The more the variation in voltage, the more the noise in the system which will impact the precision and accuracy of data, so we use binary voltage levels.
🗑
|
||||
| If you have an array sorted in ascending order, how would you find the minimum or maximum value? | Min value: first entry in the array, i.e. array[0]
Max value: last entry in the array, i.e. array[n-1], assuming n is the length of the array
🗑
|
||||
| If there are n elements in the array z, and k is defined as 0 ≤ k < n, then what’s the algorithm to retrieve the kth element in the array? What is the time complexity of this? | base address of array + (k * sizeof(int))
O(1). It requires 1 multiplication, 1 addition (i.e. 2 operations) no matter what the value of k or the length of the array is.
🗑
|
||||
| Given an unsorted integer array and its length, devise an algorithm to find if a given value is in the array or not. Return true if the value is found, and false otherwise. | Check the input to make sure the array has at least one element. If not, return nil. Set i as index of the 1st element (i = 0) and n as length of array. While i < n
Compare value at index i with value to find. If equal, return true. Else, increment i.
🗑
|
||||
| What is the time complexity of searching an unsorted array for a value? | O(n). Best case, loop will run once if the value is at array[0]. Worst case, value is not found or at the end and the loop will run the length (n) number of times. Average case, it could be n/2. The number of operations will depend on n.
🗑
|
||||
| Given an unsorted integer array and its length, devise an algorithm to find the largest integer value is in the array and return it. | Check the input to make sure the array has at least one element.
Set i and largest_value to be 1st element in the array (i = 0).
While i i< length of array; array[i] I> largest_value, update largest_value array[i]. increment i
Return largest_value.
🗑
|
||||
| What is the time complexity of finding the max or min value of an unsorted array? Sorted? | Unsorted: O(n). Need to compare each value in the array with the largest_value variable, so the loop will run n times.
Sorted: O(1). Will just need to take the value at array[0] or array[n-1]
🗑
|
||||
| Describe the algorithm for binary search. | Check the input to make sure the array has at least one element.
Set low = 0 and high = length -1
While low < high, set mid to (low + high)/2
If mid == value to find, return true.
If mid i> value, set high = mid - 1. If lower, set low = mid + 1
🗑
|
||||
| Why do we use Big O to measure the run time in terms of the number of steps in an algorithm rather than actual time to run? | The same code may take different actual time to run on different machines based on the specifications of the machine or due to other activity on the machine, so we express time complexity with respect to the input data size to see how fast it grows.
🗑
|
||||
| What is Asymptotic Notation? | How we calculate how the space and time taken by an algorithm increases with input size. ( O(1), O(n), O(2n)).
🗑
|
Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
To hide a column, click on the column name.
To hide the entire table, click on the "Hide All" button.
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Created by:
snailssnooze123
Popular Computers sets