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.
