PART ONE: Please answer the following questions:
-
Describe the purpose of Big 0.
It is used to describe how long an algorithm will take to run if it takes as long as possible. If you are searching for a number in an array, it assumes that the algorithm will find the number at the very end of the algorithm running.
-
What 2 things does it measure?
Time and input
-
Which of the following shows Big O time complexity in order?
a) O(1), O(n log n), O(log n), O(n), O(n^2)
b) O(1), O(log n), O(n), O(n log n), O(n^2)
c) O(1), O(log n), O(n log n), O(n), O(n^2)
b) O(1), O(log n), O(n), O(n log n), O(n^2)
-
Which of these algorithm(s) run in O(log n) time?
Binary Search
Bubble Sort
Quick Sort (average case)
Linear Search
Binary
-
Select the best time complexity that even the most efficient sort algorithm can have.
O(log n)
O(n log n)
O(n)
O(n^2)
O(log n)
-
Describe what sets these these 3 complexities apart from each other: O(1), O(n) and O(n^2)
O(1) will always run a set amount of times and is not determined by the size of the input, O(n) is linear and will run as many times as the input dictates, O(n^2) runs for the length of the input, and for each item runs the same number of times as the input
-
How would you recognize O(log n) and O(n log n) time complexities in a function?
If you see the length being split in half then running the loop on the array again it is likely O(log n), if the loop still has to run through the entire array
PART TWO: In a new file, write examples of algorithms/functions for each of the Big O complexities below. Upload your file to your repository when complete and submit in Learn --> Exercises.
1. O(1)
2. O(n)
3. O(n^2)