2.3.1 Algorithms - Aaron Flashcards
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.
