Algorithm Analysis

Edited by TheGuyLoveNY, Jen Moreau

Ad

Algorithm Analysis:

Time Complexity: Time complexity also known as "Running Time" is a tool to measure the performance of the algorithm. Time complexity tells us how much time an Algorithm takes to run. There are 3 techniques that are used to find Time complexity of an algorithm.

Was this helpful? Yes | No| I need help
  • Big "O": Big O is specifically used to describe worst case scenario of an algorithm. It indicated the maximum time an algorithm will take to execute.

O(1) Indicated that the program will run at a constant speed regardless of the input size. For example : x+y=z; >> O(1) means Constant.

  • Big "": Big indicated the minimum time an algorithm takes to executed with a given number of input size. Asymptotically Big represents Lower Bound.
  • Big "": Big represents Tight bound, Asymptotically. It indicated the average time taken by an algorithm to execute for a given input size.

Examples: Let's consider an example to understand Time complexity of Big "O":

A sample program :

4 1.png

As you can see from the example, the Assignment and arithmetic operations are considered constant thus are represented with O(1). Secondly, In the loop where it's "I<n", Here the variable "I" is dependent on the input variable "n". So the larger the input size n is the longer the program will run hence it is not constant i.e O(n).

Was this helpful? Yes | No| I need help

Now, Let us calculate the time complexity of the above program:

Big "O": O(1) + O(n)

= O( 1 + n)

Thus by ignoring the constant O(1), We can write:

= O(n)

Hence the Time complexity is O(n). Let's take another example to understand Time complexity better:

5 1.png

We can conclude that there is two Loop, Both, the Inner loop and the outer loop are dependent on the input size 'n'. So we have two O(n) and two constant O(1).

Here is how to calculate the time complexity:

Big "O": ( O(1) + O(n) + O(n) )

= O ( 1+ n + n)

Ignoring the constant O(1), we get:

= O ( n2)

Hence, the time complexity of the above program is O ( n2).

It is important to remember, That in nested loops , Outer loop will represent O(n) if it depends on the input size. Whereas, the inner loop will represent O(logn) if it depends on twice the input size or half of the input size.

Was this helpful? Yes | No| I need help

6 1.png

Complexity Analysis:

Complexity analysis is the analysis of algorithm that determines how much amount of resources are needed. These resources can be time: the number of milliseconds a program takes to execute, or the the resources can be memory, i.e number of bytes the program takes to run.

Was this helpful? Yes | No| I need help

Analysis of algorithm:

  • Simple statements : These are the statements that take constant time to execute. The time complexity for simple statements: s1, S2, S3, … , sk, is O(1), which is constant. These statements are constant as long as the number of statements(k) is constant, meaning the number of statements don't change at run time, which is very likely.
  • Loops : Loop statements are not constant and thus Its complexity is not constant as well. The loop's time complexity depends on the numbers of time the loop will iterate.

For example:

for( I = 0; I < n ; I++) { //something. }

Here, The loop's index variable "I" is dependent on the input variable "n", Hence the time complexity of this loop is O(n).

  • Nested Loops: Nested loop refers to Loop inside another loop. This often gets confusing due to the fact that the inner loop will execute exponentially, depending on the outer loop.

Because of this, the time complexity will greatly vary For example:

for( I = 0; I < n ; I ++) { for( j = 0 ; j < I; j++) { //Inner loop statement. } }

Here, The Outer loop runs "n" times since it's dependent on the nth value. Whereas, the inner loop depends on the outer loop and that's where it executes exponentially. So, the time complexity of this Nested loop will be O(n2).

Was this helpful? Yes | No| I need help
  • Lower order terms: While finding time complexity, we should always ignore lower order term. Now, What is lower order term? You may ask. Well, Constant expression or simple statements gives O(1), which has lower preference over O(n), which has higher priority over constant O(1). Hence, O(1) is the lower order term in this case.

For example:

Time complexity  : O(1) + O(1) + O(n)

Here, we have two lower order terms, i.e O(1). Hence, we ignore them. So, the final answer :

Time Complexity : O(n)

Another case: Similarly, Consider this next case.

Time Complexity : O(1) + O(n) + O(n2) Here, Again, the lower order term is O(1). So we remove O(1) out of the equation.

Now, Time Complexity : O(n) + O(n2)

If we look closely, we can figure out that O(n) is a lower order term and can be removed. Finally, Time Complexity  : O(n2)

Asymptotic Complexity:

As discussed, we should concentrate on the higher term and should remove the lower term out of the equation. Similarly, for Asymptotic complexity, we only focus on higher value of n and ignore the rest of the term. It is important to remember, There can be only one term left to define the complexity, That is why we keep removing the lower order term until the highest order term is left.

Was this helpful? Yes | No| I need help

Here is the Asymptotic complexity for all the sort we have come across so far.

  • Merge sort : Best case.
  • Insertion sort : Average case.
  • Selection sort : Worst case.

This article is part of a series on 'Design and Algorithm Analysis'. Read the full series here:

1) Design and Algorithm Analysis Overview

2) Algorithm_Analysis

3) Algorithm Sorting

4) Algorithm Graph in Data Structure

5) Types and Styles of Algorithm Searchs

6) Types of Algorithm Laws

7) Design and Algorythm of Dynamic Programming

Referencing this Article

If you need to reference this article in your work, you can copy-paste the following depending on your required format:

APA (American Psychological Association)
Algorithm Analysis. (2017). In ScienceAid. Retrieved Oct 23, 2017, from https://scienceaid.net/Algorithm_Analysis

MLA (Modern Language Association) "Algorithm Analysis." ScienceAid, scienceaid.net/Algorithm_Analysis Accessed 23 Oct 2017.

Chicago / Turabian ScienceAid.net. "Algorithm Analysis." Accessed Oct 23, 2017. https://scienceaid.net/Algorithm_Analysis.

If you have problems with any of the steps in this article, please ask a question for more help, or post in the comments section below.

Comments

ScienceAid welcomes all comments. If you do not want to be anonymous, register or log in. It is free.

Article Info

Categories : Design and Algorithm Analysis

Recent edits by: TheGuyLoveNY

Share this Article:

Thanks to all authors for creating a page that has been read 31 times.

Do you have a question not answered in this article?
Click here to ask one of the writers of this article
x

Thank Our Volunteer Authors.

Would you like to give back to the community by fixing a spelling mistake? Yes | No