The main resources are:
• Running Time
• Memory Usage
• Communication Bandwidth

**How do you analyses an algorithm?**

Algorithm analysis refers to the process of determining how much computing time and storage that algorithms will require. In other words, it’s a process of predicting the resource requirement of algorithms in a given environment. In order to solve a problem, there are many possible algorithms. One has to be able to choose the best algorithm for the problem at hand using some scientific method. To classify some data structures and algorithms as good, we need precise ways of analyzing them in terms of resource requirement. The main resources are:

• Running
Time

• Memory
Usage

• Communication
Bandwidth

Running
time is usually treated as the most important since computational time is the
most precious resource in most problem domains.

There are
two approaches to measure the efficiency of algorithms:

• Empirical:
Programming competing algorithms and trying them on different instances.

• Theoretical: Determining the quantity of resources required mathematically (Execution time, memory space, etc.) needed by each algorithm.

However, it is difficult to use actual clock-time as a consistent measure of an algorithm’s efficiency, because clock-time can vary based on many things. For example,

• Specific
processor speed

• Current
processor load

• Specific
data for a particular run of the program

o Input
Size

o Input Properties

•
Operating Environment

Accordingly, we can analyze an algorithm according to the number of operations required, rather than according to an absolute amount of time involved. This can show how an algorithm’s efficiency changes according to the size of the input.

**Complexity Analysis**

Complexity
Analysis is the systematic study of the cost of computation, measured either in
time units or in operations performed, or in the amount of storage space
required.

The goal
is to have a meaningful measure that permits comparison of algorithms
independent of operating platform.

There are
two things to consider:

• Time Complexity: Determine the approximate number of operations required to solve a problem of size n.

• Space Complexity: Determine the approximate memory required to solve a problem of size n. Complexity analysis involves two distinct phases:

• Algorithm Analysis: Analysis of the algorithm or data structure to produce a function T that describes the algorithm in terms of the operations performed in order to measure the complexity of the algorithm.

• Order
of Magnitude Analysis: Analysis of the function T (n) to determine the general
complexity category to which it belongs. There is no generally accepted set of
rules for algorithm analysis. However, an exact count of operations is commonly
used.

**Analysis Rules:**

1. We assume
an arbitrary time unit.

2. Execution
of one of the following operations takes time 1:

•
Assignment Operation

• Single
Input/Output Operation

• Single
Boolean Operations

• Single
Arithmetic Operations

•
Function Return

3. Running
time of a selection statement (if, switch) is the time for the condition
evaluation + the maximum of the running times for the individual clauses in the
selection.

4. Loops:
Running time for a loop is equal to the running time for the statements inside
the loop * number of iterations.

The total
running time of a statement inside a group of nested loops is the running time
of the statements multiplied by the product of the sizes of all the loops.

For
nested loops, analyze inside out.

• Always
assume that the loop executes the maximum number of iterations possible.

5.
Running time of a function call is 1 for setup + the time for any parameter
calculations + the time required for the execution of the function body.

Examples:

1. int
count(){ int k=0;

cout<<
“Enter an integer”; cin>>n;

for
(i=0;i k=k+1; return 0;}

Time
Units to Compute

-------------------------------------------------

1 for the
assignment statement: int k=0

1 for the
output statement.

1 for the
input statement. In the for loop:

1
assignment, n+1 tests, and n increments.

n loops
of 2 units for an assignment, and an addition. 1 for the return statement.

-------------------------------------------------------------------

T (n)=
1+1+1+(1+n+1+n)+2n+1 = 4n+6 = O(n) 2. int total(int n)

{

int
sum=0;

for (int
i=1;i<=n;i++) sum=sum+1;

return
sum;

}

Time
Units to Compute

-------------------------------------------------

1 for the
assignment statement: int sum=0 In the for loop:

1
assignment, n+1 tests, and n increments.

n loops
of 2 units for an assignment, and an addition. 1 for the return statement.

-------------------------------------------------------------------

T (n)= 1+
(1+n+1+n)+2n+1 = 4n+4 = O(n) 3. void func()

{

int x=0;
int i=0; int j=1;

cout<<
“Enter an Integer value”; cin>>n;

while (i
x++; i++;

}

while (j

{

j++;

}

}

Time
Units to Compute

-------------------------------------------------

1 for the
first assignment statement: x=0;

1 for the
second assignment statement: i=0;

1 for the
third assignment statement: j=1;

1 for the
output statement.

1 for the
input statement.

In the first while loop:

n+1 tests

n loops of 2 units for the two increment (addition) operations

In the second while
loop:

n tests

n-1
increments

-------------------------------------------------------------------

T (n)=
1+1+1+1+1+n+1+2n+n+n-1 = 5n+5 = O(n) 4. int sum (int n)

{

int
partial_sum = 0;

for (int
i = 1; i <= n; i++) partial_sum = partial_sum +(i * i * i); return
partial_sum;

}

Time
Units to Compute

-------------------------------------------------

1 for the
assignment.

1
assignment, n+1 tests, and n increments.

n loops
of 4 units for an assignment, an addition, and two multiplications. 1 for the
return statement.

-------------------------------------------------------------------

T (n)=
1+(1+n+1+n)+4n+1 = 6n+4 = O(n)

Formal
Approach to Analysis

In the
above examples we have seen that analysis so complex. However, it can be
simplified by using some formal approach in which case we can ignore
initializations, loop control, and book keeping.

**For Loops: **Formally

• In general, a for loop translates to a summation. The index and bounds of the summation are the same as the index and bounds of the for loop.

• Suppose
we count the number of additions that are done. There is 1 addition per
iteration of the loop, hence N additions in total.

**Nested Loops: **Formally

• Nested
for loops translate into multiple summations, one for each for loop.

• Again,
count the number of additions. The outer summation is for the outer for loop.

Consecutive
Statements: Formally

• Add the
running times of the separate blocks of your code

Conditionals:
Formally

• If
(test) s1 else s2: Compute the maximum of the running time for s1 and s2.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Linear Data Structures : How do you analyses an algorithm? |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.