Analysis, Design and Comparison of Algorithms:
Analysis of algorithms:
When developing an algorithm, there are 2 different things to check:
Time complexity
Space complexity
Time complexity:
The time complexity of an algorithm is how much time it requires to solve a particular problem. The time
complexity is measured using a notation called big-o notation, which shows the effectiveness of the
algorithm. It shows an upper limit for the amount of time taken relative to the number of data elements
given as an input. This is good, because it allows you to predict the amount of time it takes for an
algorithm to finish given the number of data elements.
You can think of this as a graph, as the number of data elements entered against the time taken to
complete the algorithm. This will be helpful for showing the relationships between time and the number
of elements inputted. These are shown below.
Big-O notation is written in the form O(n), where n is the relationship between n: the number of
inputted entities, and O(n) is the time relationship. Below are examples of different big-O notations:
Big-O notation Name Description
O(1) Constant time complexity The amount of time taken to complete an algorithm
is independent from the number of elements
inputted.
O(n) Linear time complexity The amount of time taken to complete an algorithm
is directly proportional to the number of elements
inputted.
O(n2) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the square of the number
of elements inputted.
O(nn) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the elements inputted to
the power of n.
O(2n) Exponential time complexity The amount of time taken to complete an algorithm
will double with every additional item.
O(log n) Logarithmic time complexity The amount of time taken to complete an algorithm
will increase at a smaller rate as the number of
elements inputted.
When calculating the time complexity, you should think logically through the algorithms. Below are a
few examples:
Algorithm example Big-O notation
This example is unrelated to the number of items Constant time:
inputted: This will always take the same amount of time to
For example: complete regardless of the number of values
Print(“hello”) inputted.
, This example is directly proportional to the Linear Time Complexity:
number of items inputted: The time taken to complete the algorithm is
For example: related to the number of items inputted.
inuttedValue = [a,b,c,…,n]
for I in range(len(inputtedValue)): The number of operations completed was
print(“hello”) proportional to the inputted value.
This example is proportional to the number of Polynomial Time Complexity:
items inputted: The amount of time taken to complete the
For example: algorithm is proportional to the number of items
inputtedValue[a,b,c…n] inputted to the power of n.
for I in range(len(inputtedValue)):
for I in range(len(inputtedValue)): The power given to the polynomial is the same as
print(“hello”) the number of embedded loops.
This example is exponentially proportional to the Exponential Time Complexity:
number of items inputted: The amount of time taken to complete the
For example: algorithm is proportional to 2 to the power of the
Recursive algorithms that solve a problem of size number of items inputted.
N by recursively solving 2 smaller problems f size
N-1 This is common with recursive algorithms solving
2 smaller problems of size n-1
This example is logarithmically related to the Logarithmic time complexity
number of items inputted:
for example:
a divide and conquer algorithm is a good example
of this, the number of items you have to search
through gets halved each time.
Time Complexity Graphs:
Constant Time Complexity:
, Linear Time Complexity:
Polynomial Time Complexity:
Exponential Time Complexity:
Analysis of algorithms:
When developing an algorithm, there are 2 different things to check:
Time complexity
Space complexity
Time complexity:
The time complexity of an algorithm is how much time it requires to solve a particular problem. The time
complexity is measured using a notation called big-o notation, which shows the effectiveness of the
algorithm. It shows an upper limit for the amount of time taken relative to the number of data elements
given as an input. This is good, because it allows you to predict the amount of time it takes for an
algorithm to finish given the number of data elements.
You can think of this as a graph, as the number of data elements entered against the time taken to
complete the algorithm. This will be helpful for showing the relationships between time and the number
of elements inputted. These are shown below.
Big-O notation is written in the form O(n), where n is the relationship between n: the number of
inputted entities, and O(n) is the time relationship. Below are examples of different big-O notations:
Big-O notation Name Description
O(1) Constant time complexity The amount of time taken to complete an algorithm
is independent from the number of elements
inputted.
O(n) Linear time complexity The amount of time taken to complete an algorithm
is directly proportional to the number of elements
inputted.
O(n2) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the square of the number
of elements inputted.
O(nn) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the elements inputted to
the power of n.
O(2n) Exponential time complexity The amount of time taken to complete an algorithm
will double with every additional item.
O(log n) Logarithmic time complexity The amount of time taken to complete an algorithm
will increase at a smaller rate as the number of
elements inputted.
When calculating the time complexity, you should think logically through the algorithms. Below are a
few examples:
Algorithm example Big-O notation
This example is unrelated to the number of items Constant time:
inputted: This will always take the same amount of time to
For example: complete regardless of the number of values
Print(“hello”) inputted.
, This example is directly proportional to the Linear Time Complexity:
number of items inputted: The time taken to complete the algorithm is
For example: related to the number of items inputted.
inuttedValue = [a,b,c,…,n]
for I in range(len(inputtedValue)): The number of operations completed was
print(“hello”) proportional to the inputted value.
This example is proportional to the number of Polynomial Time Complexity:
items inputted: The amount of time taken to complete the
For example: algorithm is proportional to the number of items
inputtedValue[a,b,c…n] inputted to the power of n.
for I in range(len(inputtedValue)):
for I in range(len(inputtedValue)): The power given to the polynomial is the same as
print(“hello”) the number of embedded loops.
This example is exponentially proportional to the Exponential Time Complexity:
number of items inputted: The amount of time taken to complete the
For example: algorithm is proportional to 2 to the power of the
Recursive algorithms that solve a problem of size number of items inputted.
N by recursively solving 2 smaller problems f size
N-1 This is common with recursive algorithms solving
2 smaller problems of size n-1
This example is logarithmically related to the Logarithmic time complexity
number of items inputted:
for example:
a divide and conquer algorithm is a good example
of this, the number of items you have to search
through gets halved each time.
Time Complexity Graphs:
Constant Time Complexity:
, Linear Time Complexity:
Polynomial Time Complexity:
Exponential Time Complexity:
