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.
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.
