This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
In the previous article on our introduction to algorithms, we spoke about algorithmic analysis. And in this article we will go in depth.
Writing An Algorithm
Before we can analyze an algorithm, we need to write it first. So how do we write it?
Algorithm Swap(a,b):
temp = a
a = b
b = temp
return
Above is a simple algorithm, I have borrowed some Python syntax. I said in the previous articles algorithms are syntax independent, which I still stand by.
I just borrowed the Python syntax so we can see where the name of the algorithm starts. The commands within the algorithm and where the algorithm ends.
We do not have variable declarations as they are not needed, syntax to start a function, etc.
Analyzing An Algorithm
Now that we now how to write an algorithm, we can move on to analyzing an algorithm.
We need to consider the following for algorithms;
- Time
- Memory
- Data Consumption(How much data your algorithm consumes)
- Power Consumption
We will only be focusing on time and space analysis for our algorithmic article series. These two are measured in Big O notation
Time Taken By An Algorithm
How long will an algorithm take to complete a specific task.
Say we want an algorithm to find the shortest path between A.B.C.D and return the answer to the user.
We will write this algorithm and after that check how much time it takes to complete this task. We do not want algorithms that take long to complete a task.
Let us start with statements;
A simple direct statement in an algorithm takes one unit of time.
Example:
temp = a, this is one unit of time.
a = b, this is also another unit of time.
The above statements are very direct, straight to the point and not calling any other algorithm, hence they are not nested statements.
Let’s analyze the time analyses of our above function:
Algorithm swap(a,b):
temp = a
a = b
b = temp
return
We count all of our statements, temp = a, a = b and b = temp. Each of these statements take 1 unit of time.
temp = a (1)
a = b (1)
b = temp (1)
So our f(n) is 3, which is a constant value. Any integer number is considered as a constant value.
We can already see the pattern that all assignment statements take one unit of time.
We can represent constant values with O(1), all the integer numbers are O(1).
Lets analyze the space complexity of this algorithm:
To analyze space complexity we look at the variables, in our case we have a,b, and temp.
All in all we have used three variables. Our space complexity is O(3).
We can calculate time complexity in two ways, first one being frequency count and the other asymptotic notations.
Frequency Count
Frequency count specifies the number of times a statement is to be executed, so how many times the statement within our algorithm is executed.
I generally follow this four rules basis:
- For comments and declarations the step count is 0, as comments are not executed, and declarations are not needed while writing the algorithm.
- For the return and assignment statement the step count is 1, assignment statement is simply assigning a left hand value to a right hand value. While the return statement is just returning a value.
- Only consider higher order exponents. E.g.; 3n² +4n. We will only consider 3n² as it has the higher order exponent.
- Ignore the constant value multipliers. We are left with 3n², our constant multiplier is 3, we ignore it and are left with n². Our time complexity is O(n²).
Lets get our feet wet with some examples;
Algorithm Sum(A,n):
s = 0
for i in A:
s = s + A[i]
return s
The algorithm above is an array of a certain size, let us say the array has 4 elements within it. The elements within the array are 9,6,10,5,6
A is our array and n is the number of elements. The algorithm above is finding the sum of all the elements in the array. We want to find the time taken by the algorithm, we will do this by finding the frequency count method, and our four rules.
Breaking down the algorithm;
Initially i is 0, as we have a for loop we know our algorithm is repeating a certain number of times, and this number of times is n.
Lets count with it;
i = 0
i = 1
i = 2
i = 3
i = 4
i = 5
The loop stops and returns the value at s, this is when the algorithm is done looping. The logic of this goes as follows; i = 0 and 0 < n, i = 1 and 1<n, i = 2 and 2 < n, i = 3 and 3 < n, i = 4 and 4 < n, i = 5 and 5 > n. The loop will stop at i = 5 as 5 is greater than n.
The condition is checked 5 times all in all. Four times the condition was true i < n and the fifth time false, i > n. Our loop is executing for n + 1 times. How would we count the For loop, as it executes n + 1 times then we count it as n+1 steps.
Summarizing;
Algorithm Sum(A,n): 0
s = 0 -1
for i in range(A): n+1
s = s + A n(1)
return s 1
The first line of our algorithm;
Algorithm Sum(A,n): this does not count for anything as it is a declaration and the step count is 0.
The second line of our algorithm;
s = 0; this is given a value of 1 in the step count frequency method as it is an assignment statement.
The third line in our algorithm;
for i in range A: the statement will tell our interpreter that loop inside the array until you complete the range of the array. This means we will loop n + 1 times.
The fourth line in our algorithm;
s = s + A[i]; this an assignment statement as we are assigning s to s + A[i], and because this statement is within a loop, we will assign n as its value.
The 5th line in our algorithm;
return s; as it is a return statement then the step count is 1
Tally up our values;
1+n+1+n+1 = 2n + 3
2n + 3
We only consider the higher order exponents, this means we will only be left with 2n.
Then we will ignore will constant multiplier, and we will be left with n, hence we be left with O(n).
Moving on to space complexity of the algorithm. We only count the variables in our algorithm.
We have s, A ,n, i;
A = n ( A is our array which has n elements, hence it is n)
s = 1 ( s only occupies one element)
n =1 ( n only occupies one element)
i = 1 ( i only occupies one element)
Tally count;
n+1+1+1+1 = n + 4, we only consider the higher order exponents and are left with n.
O(n).
Example 2:
Algorithm Add(A,B,n):
for i in range(A):
for j in range(A):
C = A + B
return
With our example two we have two nested loops, the outer For loop and the inner for loop. Additionally we have a metrices or what is known as a two dimensional array.
Which are size 3 * 3, also expressed as n * n, hence we can say our above algorithm finds the sum of two metrices.
Algorithm ADD(A,B,n): 0
for i in range(A): n+1
for j in range(A): n(n+1)
c = A + B n(n)
return 1
Starting from the first statement, we ignore Algorithm ADD(A,B,n):
Second line we have our outer for loop and our step count is n+1.
Third line we have our inner for loop, which has n as it is within a loop, in this case the outer loop. As it is a loop itself we also assign n+1 to it. The second loop will have n as it is within a loop and n+1 as it is a loop itself(it loops n+1 times even thou it is within a loop).
The fourth line we have c = A + B, it is within two for loops, for the first loop we will assign n and the second loop another n.
The last line we have< return 1, it returns after the For loop.
Tally: n + 1 +n² +1 + n² + 1
2n² n +3
Only consider higher order exponents, we will be left with 2n².
2n², we ignore the multiplier constant.
We are left with n², hence we will have O(n²).
Additional Reading:
Frequency-counting - Basic Articles
Algorithmic Analysis was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
Thenjiwe kubheka | Sciencx (2021-10-11T11:22:53+00:00) Algorithmic Analysis. Retrieved from https://www.scien.cx/2021/10/11/algorithmic-analysis/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.