Finding the Big O Notation of an Algorithm: Part 1

Algorithms are like art; they should also be analyzed in an artistic manner.How long will an algorithm take to computeHow much space will it take to run the algorithmNetwork and data transfer needed for the algorithmPower Consumption needed to run the …

Algorithms are like art; they should also be analyzed in an artistic manner.

  • How long will an algorithm take to compute
  • How much space will it take to run the algorithm
  • Network and data transfer needed for the algorithm
  • Power Consumption needed to run the algorithm.

At a basic level, we will only look at the time and space complexity

There are two methods commonly used to find the Time and Space Complexity of an Algorithm. Namely “ The Frequency Method” and “Assymptotic Notation”.

In this article, we will be diving into The Frequency Method.

Source: Joshua Earle via Unsplash.com

What is Frequency Count?

This is basically the number of times a corresponding statement is executed. I live by four rules when implementing frequency count.

  1. When looking at comments and declarations, our step count remains zero. Why is this? Well comments are never executed by the computer. There are to remind us of something or communicate something to the next programmer. Secondly no need to count declarations at algorithm stage. We only consider algorithms at programming stage.

2. We count return statements and assignment statements as step count 1, just Return statement just returns a value and an assignment statement is symmetrical, hence it remains as 1.

3. Higher order exponents take priority and lower order exponents are ignored. What do I mean by this?

If I have 5n³ + 7n² + 3n + 3

We will only consider the higher order exponent which is 5n³ and ignore all the other lower order exponents.

4. Lastly we ignore all the step multipliers, we are left with 5n³, we ignore the 5 and we are left with n³. written as O(n³).

Lets get our hands dirty with some examples:

Example 1:

Algorithm Sum (A,n)
{
s = 0;
for(i = 0; i<n; i++)
{
s = s + A[i];
}
return s;
}

Above we have an algorithm that will find the sum of all numbers in the array.

We ignore the declaration, move on to the first statement s=0. We said we assign 1 to our assignment statements.

s = 0;         1

Next we move to the For loop, within the For loop we will only look at i < n, which will check how many times the loop will be executed.

for (i = 0; i < n; i++)

If n = 3; then i is initially 0. Then moves on to 1, then moves on to 2, then moves on to 3. Stops at 3!

i =0 and 0< 3

i = 1 and 1 < 3

i = 2 and 2 < 3

i = 3 and 3< 3

The condition is checked n + 1 times, that is 4 times. So our For loop will be executed n+1 times.

Now I have one last rule, I did not mention above. Every statement inside a loop is executed n times.

s = s+A[i]                    n
}
return; n
}

lets tally up our items to determine the time complexity.

1 + n + 1 +n + n

3n +2

Rule number 3 we only consider the higher order exponents, which is 3n. And rule number 4, Ignore all step multipliers.

We are left with (n), which is O(n).

Example 2:

Algorithm Add(A,B,n)
{
for(i = 0; i < n; i ++)
{
for(j = 0; j<n; j++)
{
c[i,j] = A[i,j] + B[i,j]
}
}
}

We know the outer For loop will execute n+1 times.

for( i = 0; i<n; i ++)       n+1

Then we have statements within our for loop

for(j = 0; j<n; j++)         n
{
c[i,j] = A[i,j] + B[i,j]; n
}

Statements within a loop are executed n times

But we are not yet ready to tally up our totals. We still have to count the inner for loop and the statements within the inner for loop.

for(j = 0; j<n; j++)       n(n+1)
{
c[i,j] = A[i,j] +B[i,j]; n(n)

Now we can add up everything;

n+1 +n² +1+n² = 2n² +n+2

Rule number 3 we only consider the higher order exponents, and we are left with 2n².

The last rule, we ignore all step multipliers. We are left with (n²). Which 0(n²).

Example 3

Algorithm Multiply(A,B,n)
{
for(i = 0; i< n, i ++)
{
for(j=0; j<n ; j++)
{
c[i,j] = 0;
for(k=0; k<n ; k++)
{
c[i,j] = c[i,j] + A[i,k] * B[k,j];
}
}
}
}

We begin with our outer For loop which will execute n+1 times;

For(i = 0; i<n; i++)

Then we know all statements within a loop will execute n times. Each of the statements below will execute n times.

for(j=0; i,n;i++)
{
for(j=0;j<n;j++)
{
c[i,j] = 0
for(k = 0; k<n,k++)
{
c[i,j] = c[i,j] + A[i,k] * B[k,j];

But we have 3 inner loops that will execute n+1 times. And all the statements within them will execute n times each. So lets tally up the total.

n+1+n²+1+n²+n³+1+n³ = 2n³ +2n²+n+3

We only consider the higher order polynomials, we are left with;

2n³

We ignore the step multipliers. We are left with (n³). Expressed as Big O(n³).

Space Complexity

This id the memory needed for the algorithm. To determine the space complexity of an algorithm, we count all the variables.

Example 1

Algorithm Sum(A,n)
{
s = 0
for(i = 0; i < n; i ++)
{
s = s+ A[i]
}
return s;

Variables;

s= is just a normal variable so we assign 1 as the step count

i= is also a normal variable, we will also assign 1 as a step count

A[]= is an array, with n elements so we assign n as the step count.

Tally us, we have n + 2, we only consider the higher order exponents, so we are left with n.

Example 2:

Algorithm Add(A,B,n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
c[i,j] = A[i,j] + B[i,j]
}
}
}

Variables:

A,B and C are metrices, hence if n=3 then we will get 3*3. Or n*n = n²

A []= n²

B [] n²

n = 1

i = 1

j = 1

c [] = n²

Tally up everything; n²+n²+n² + 1+1+1 = 3n²+3

We only consider the higher order exponent 3n². Which is Big O(n²).


Finding the Big O Notation of an Algorithm: Part 1 was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.


Print Share Comment Cite Upload Translate
APA
Thenjiwe kubheka | Sciencx (2024-03-28T17:19:31+00:00) » Finding the Big O Notation of an Algorithm: Part 1. Retrieved from https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/.
MLA
" » Finding the Big O Notation of an Algorithm: Part 1." Thenjiwe kubheka | Sciencx - Friday September 3, 2021, https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/
HARVARD
Thenjiwe kubheka | Sciencx Friday September 3, 2021 » Finding the Big O Notation of an Algorithm: Part 1., viewed 2024-03-28T17:19:31+00:00,<https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/>
VANCOUVER
Thenjiwe kubheka | Sciencx - » Finding the Big O Notation of an Algorithm: Part 1. [Internet]. [Accessed 2024-03-28T17:19:31+00:00]. Available from: https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/
CHICAGO
" » Finding the Big O Notation of an Algorithm: Part 1." Thenjiwe kubheka | Sciencx - Accessed 2024-03-28T17:19:31+00:00. https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/
IEEE
" » Finding the Big O Notation of an Algorithm: Part 1." Thenjiwe kubheka | Sciencx [Online]. Available: https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/. [Accessed: 2024-03-28T17:19:31+00:00]
rf:citation
» Finding the Big O Notation of an Algorithm: Part 1 | Thenjiwe kubheka | Sciencx | https://www.scien.cx/2021/09/03/finding-the-big-o-notation-of-an-algorithm-part-1/ | 2024-03-28T17:19:31+00:00
https://github.com/addpipe/simple-recorderjs-demo