2.3.1 Comparison of Algorithms (complexities) Flashcards
Time Complexity
The amount of time required to solve a particular problem.
Why is it good to use time complexity?
You can predict the amount of time it takes for an algorithm to finish, given the number of data elements.
Describe constant time complexity O(1)
The time taken for an algorithm to complete is independent from the number of elements inputted.
Describe linear time complexity. O(n)
The time taken for an algorithm to complete is directly proportional to the number of elements inputted.
Describe polynomial time complexity. O(n^x)
The time taken for an algorithm to complete is directly proportional to the number of elements to the power x.
Describe exponential time complexity. O(2^n)
The time taken for an algorithm to complete will double with every additional item.
Describe logarithmic time complexity. O(logn)
The time taken for an algorithm to complete will increase at a smaller rate as the number of elements inputted increases.
Determine the time complexity of the following code.
~~~
print(“hello”)
~~~
Constant Time
O(1)
Determine the time complexity of the following code.
~~~
inputtedValue = [a,b,c, … , n]
for i = 0 to inputtedValue.length() -1
print(“hello”)
next i
~~~
Linear Time Complexity
O(n)
Determine the time complexity of the following code
~~~
inputtedValue = [a,b,c, … , n]
for i = 0 to inputtedValue.length() -1
for j = 0 to inputtedValue.length() - 1
print(“hello”)
next j
next i
~~~
Polynomial Time Complexity
O(n^2)
Power = Number of embedded loops
Determine the time complexity of a recursive algorithm which solves a problem of Size N by recursively solving two smaller problems of size N-1
Exponential Time Complexity
O(2^n)
Determine the time complexity of a divide and conquer algorithm, which halves the number of items that needs to be searched through every time.
Logarithmic Time Complexity
O(log n)
What is the space complexity of an algorithm?
The amount of storage the algorithm takes.
What two things are incredibly important when analysing the effectiveness of a program?
Time complexity and space complexity
Does either time complexity or space complexity have more priority than the other?
No. Decide whats more important when designing the algorithm.
What is an algorithm?
A series of steps that completes a task.
How do we reduce space complexity?
Make sure you perform all of the changes on the original pieces of data.
How do we reduce the time complexity?
- Try to reduce the number of embedded loops.
- Try to reduce the number of items you have to complete operations on
Best/Average/Worst Time Complexities: Linear Search
BEST: O(1)
AVERAGE: O(n)
WORST: O(n)
Best/Average/Worst Time Complexities: Binary Search Array
BEST: O(1)
AVERAGE: O(logn)
WORST: O(logn)
Best/Average/Worst Time Complexities: Binary Search Tree
BEST: O(1)
AVERAGE: O(logn)
WORST: O(n)
Best/Average/Worst Time Complexities: Hashing
BEST: O(1)
AVERAGE: O(1)
WORST: O(n)
Best/Average/Worst Time Complexities: Breadth/Depth first
BEST: O(1)
AVERAGE: O(V+E) [Vertices + Edges]
WORST: O(V^2)
Best/Average/Worst Time Complexities: Bubble Sort
BEST: O(n)
AVERAGE: O(n^2)
WORST: O(n^2)
Best/Average/Worst Time Complexities: Insertion Sort
BEST: O(n)
AVERAGE: O(n^2)
WORST: O(n^2)
Best/Average/Worst Time Complexities: Merge Sort
BEST: O(nlogn)
AVERAGE: O(nlogn)
WORST: O(nlogn)
Best/Average/Worst Time Complexities: Quick Sort
BEST: O(nlogn)
AVERAGE: O(nlogn)
WORST: O(n^2)
Compare the space complexities of the four sorting algorithms:
Bubble
Insertion
Merge
Quick
Bubble O(1)
Insertion O(1)
Merge O(n)
Quick O(logn)
