Algorithm Performance Analysis

Whenever a new algorithm is designed, the key fact on which every resource selection of the software implementation is depended upon is the performance analysis. This actually let the programmer/system designer know about the resource consumption by the algorithm. The performance analysis consist up of two main properties:

1. Space Complexity

2. Time complexity

Space Complexity

This analyzes the amount of memory and algorithm needs to run to completion. Speed needed by any algorithm is seen to be the sum of the following components:

a) Fixed part :- This factor is independent of the character of the input and output. This part typically includes the instruction space, space of simple variables and fixed sized component variables, space for constants etc.

b) Variable part :- This consist of the space needed by component variables whose size is dependent on the particular problem instance being solved, the space needed by referenced variables and the recursion stack space included under this.

So overall the fixed part is the one that has a static storage variables whereas variable part consist of those variable which are declared & defined on runtime, also this includes the memory used for recursion stack space used for storing recursive function calls.

So we can say that space requirement S(P) of any algorithm ‘P’ can be written as:

S(P) = C + Sp

Where C -> constant space or fixed part

Sp -> Instance characteristics or variable part

When analyzing the space complexity of an algorithm main concentration is solely on estimating ‘Sp’ i.e. instance characteristics

For any given problem:

(i) We first need to determine which instance characteristics to use to measure the space requirement and this is always problem specific.

(ii) Also it is dependent on quantities related to the number and magnitudes of the inputs and output of algorithms.

(iii) Sometimes more complex measures of the inter-relationship among the data items are used.

Time Complexity

This is the amount of computer time an algorithm needed to run to completion and is most of the time dependent on the Line of code written in any programming language.

Or formally said

The time T(p) taken by a program ‘p’ is the sum of the compile time and the run or execution time. The compile time(static time) does not depend on the instance characteristics, so runtime of the program is mainly considered & is denoted by Tp (instance characteristics)

Some important factors that effects the execution time of a particular program/algorithm are:

1. Characteristics of compiler used to compile the program

2. Machine on which the program is executed & physically clocked.

3. Multiuser environment system

4. No of program steps….. this is the most highlighted factor because it is also responsible for occupying the instruction space which affects the space complexity, but as the compilers are getting advanced this problem is overcome by optimizing the instruction during the compilation process.

Program Step: It is loosely defined as a syntactically or semantically meaningful segment of a program that has an execution time, which is independent of instance characteristics.

The number of steps in any program statement is assigned depends on the kind of statement like, comments count as zero, an assignment statement which does not involves any calls to other algorithm subroutine is counted as one step, in iterative statements we consider the step count only for the control part of the statement including one extra cycle for last iterative call in which the conditional part becomes false and iterative control statement exits without executing the code segment.

There are two ways of determining the step count for the program to solve a particular time complexity of any problem:

1) By adding a count variable in a program initialized with zero and incrementing it after each statement is executed in that program.

2) By building a table in which we list the total number of steps contributed by each statement. This conclusion is often arrived at by first determining the number of steps per execution of the statement & frequency of each statement.

Steps per execution(S/E): The S/E of a statement is the amount by which the count changes as a result of the execution of that statement.

Above discussed topics are very basic or I would say the brief concepts for analyzing the performance of any algorithm. In next post, will try to discuss related to the asymptotic notations which actually produces the concepts closely related to mathematical inductions of analysis part and more signifies the efficiency of any algorithm.

Till then “Happy Reading”

Basics of algorithms

Design and analysis of algorithms is the core field of research in which the designing of new innovative algorithms for some specific problem domains is done and then the in depth analysis of that algorithm design is done by considering various execution factors like CPU cycle requirement, memory requirements etc. As we said Algorithm let’s start with this…..

 

What is an algorithm?

An algorithm is a finite set of instructions that if followed accomplishes a particular task. An algorithm must satisfies the following criteria

1. Input : Zero or more inputs are supplied.

2. Output: Atleast one output should be produced as result of procedure.

3. Definiteness: Each instruction should be clear and unambiguous (i.e.) not more than one meaning.

4. Finiteness: If all the instructions are traced in algorithm, then for all cases the algorithm must terminate after a finite number of steps.

5. Effectiveness: Every instruction must be very basic so that it can be carried out briefly said “Operation must be feasible”.

 

Also algorithms that are definite and effective are also called as computational procedures. Operating system is the best example for this. Operating system(OS) is designed to control the execution of jobs in such a way that when  no job are available, it do not terminate but continues in waiting state until a new job is entered. This waiting state of OS is generally known as sleeping threads.

 

What is program?

A program is the expression of an algorithm in a programming language. An algorithm can be implemented in any language as per the requirement of the process to be implemented.

 

Now whenever an algorithm is needed to be designed and analyzed generally there are following four questions that arise:

1. How to devise algorithm?[the most confusing thing among the newbies but the most interesting]

2. How to validate an algorithm?

3. How to analyze an algorithm? [this needs some sense of basic engineering mathematics and Discrete mathematics, so please brush up your very basic concepts not too much depth is required]

4. How to test a program? [this is done only after implementing the algorithm in some programming language]

 

Let us go through all the above mentioned how’s

 

How to devise an algorithm?

This is the most interesting and most sophisticated art which can never be fully automated. There are number of base techniques using which the algorithms are designed like dynamic programming, linear, non-linear techniques etc. and we are going to discuss them in future posts in detail. This is the first step which reap the seeds for analysis of the algorithm devised.

 

How to validate algorithm?

Once an algorithm is devised, it is necessary to show that it computes the correct  answer for all possible legal inputs, this process is referred as algorithm validation. The purpose of validation is to assure us that this algorithm will work correctly and independently of the issues concerning the programming language. Once the validation of method is done, a program can be written and the phase of program proving or program verification starts.

 

How to analyze algorithm?

As an algorithm is converted into a program and is exceuted, it uses the computer central processing unit to perform operations and its memory to hold the program and data. Analysis of algorithm or performance analysis refers to determining how much computing time and storage resources an algorithm requires. This analysis allows:

(i)  to make quantitative judgement about the value of one algorithm over another.

(ii) to predict whether the software implementing the algorithm will meet any efficiency constraint that exist.

During analysis of algorithm the following gategories were considered : Best case, worst Case and average case.

 

How to test a program?

Testing a program consist of two phases:

(i)  Debugging: The process of executing program on sample data set to determine whether faulty error occurs & if so, correct them.

(ii) Profiling: The process of executing correct program on datasets & measuring the time and space it takes to compute the results. This helps in optimizing the algorithms. Profiling is also known as performance measures.

 

Above all four questions actually provides an idea about the concepts that Analysis of algorithm hold. In next post will be going to discuss in detail about complexities.

 

Reference for above contents is from Cormen , sahni and wiki.

Welcome note for Design and analysis of algorithm

Dear reader,

 

Welcome to first post of this blog created for one of the core subject of the computer science field i.e. Design and Analysis of Algorithms. I have been studying this subject from last few years… one of the most interesting subject in computer science, which is actually a combination of mathematics and algorithm design techniques. Will be doing a brief or detailed discussion about various topics and will try to do in a very simple manner . so enjoy reading this… do let me know it this thing helped you out.

 

Regards

Great minds

“Happy Reading”