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? | show 🗑
|
||||
| show | Linear Search
🗑
|
||||
| What is the opposite of Linear Search? | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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? | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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.
🗑
|
||||
| show | We ignore the little parts and focus on the big parts that have the most impact.
🗑
|
||||
| show | O(n²). We ignore the x, 1, and 3 because they do not affect the run time as much as the exponent.
🗑
|
||||
| show | n²
When an algorithm is a mix of orders, the dominant order is shown and the rest are dropped.
🗑
|
||||
| show | 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? | show 🗑
|
||||
| In Big O notation, which scenarios are we most concerned with? | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | O(n²)
🗑
|
||||
| show | O(n³). It's not optimal because the steps increase exponentially as the input increases.
🗑
|
||||
| show | O(n³)
🗑
|
||||
| What is the time complexity of an algorithm with no loops? | show 🗑
|
||||
| What is constant time complexity? | show 🗑
|
||||
| What is the time complexity of an algorithm that passes an array into a function and prints the first element of the array? | show 🗑
|
||||
| What is logarithmic time? Is it efficient? | show 🗑
|
||||
| What is the time complexity of an algorithm that uses binary search? | show 🗑
|
||||
| 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? | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | O(log(n))
🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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 | show 🗑
|
||||
| What is factorial time complexity. Is it optimal for an algorithm? | show 🗑
|
||||
| Why isn't o(n!) optimal? | show 🗑
|
||||
| show | Optimizing the algorithm to take less time to run.
🗑
|
||||
| What is meant by Big O Notation for space? | show 🗑
|
||||
| Describe is O(1) space complexity. | show 🗑
|
||||
| Describe O(n) space complexity. | show 🗑
|
||||
| show | 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? | show 🗑
|
||||
| Why do computers save information in binary? | show 🗑
|
||||
| If you have an array sorted in ascending order, how would you find the minimum or maximum value? | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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? | show 🗑
|
||||
| Given an unsorted integer array and its length, devise an algorithm to find the largest integer value is in the array and return it. | show 🗑
|
||||
| show | 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. | show 🗑
|
||||
| show | 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.
🗑
|
||||
| show | 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