2.3.1 Algorithms - Aaron
No description yet. This curated deck is ready for daily study.
Card preview (20)
What is binary search?
A O (log(n)) algorithm to search a sorted list for a particular item by repeatedly halving a sublist which could contain the item.
What is the big O for constant complexity?
O (1)
How is time complexity measured?
Big O notation
What does exponential time complexity mean?
The amount of time to complete an algorithm is proportional to 2 to the power of number of items inputted.
What does logarithmic time complexity mean?
The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.
What is an algorithm?
An algorithm is a series of steps that complete a task.
What is the big O of a linear search algorithm?
O (n)
What is the big O of a binary search algorithm?
O(log(n))
What is the big O of a bubble sort algorithm?
O (n2)
What is a logarithm?
How many times a certain number is multiplied together to reach another number.
What 2 pieces of information allow you to analyse an algorithm?
• Time Complexity • Space Complexity
What is meant by the time complexity of an algorithm?
The amount of time required to solve a particular problem.
What does a linear time complexity mean?
The amount of time taken to complete an algorithm is independent from the number of elements inputted.
What does a constant time complexity mean?
The amount of time taken to complete an algorithm is independent to the number of inputted elements.
What is space complexity?
The space complexity is the amount of storage space an algorithm takes up.
How do you reduce the space complexity?
Try to complete all of the operations on the same data set
How do you reduce the time complexity of an algorithm?
You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer
What does time complexity scale within an algorithm?
The number of individual steps taken.
How do we write big O notation?
O(n^x) where x is the highest power of n the algorithm reaches.
What is the Big-O notation good for?
It allows you to predict the amount of time taken to solve an algorithm given the number of items stored.