What is an Algorithm

An algorithm is a set of rules that defines how a particular problem can be solved in finite number of steps is known as algorithm. An algorithm is a description of steps or instructions required to solve a given problem. An algorithm also specifies the sequence in which the steps are to be performed.

Example: Write a Algorithm to find sum of 2 numbers.
Step 1: Start
Step 2: Read the two number say A and B.
Step 3: Add A and B and store in C.
Step 4: Print C
Step 5: Stop

Space Complexity

The space complexity of an algorithm is the amount of memory it needs to run the program for its completion. This is an important factor in early times when space is very costly. At that time, one is interested in finding algorithm, which uses less memory. Algorithm, which uses less memory, is considered more efficient than others. The space is needed by each of these algorithms is seen to be the sum of the following components:

1. A fixed part that is independent of the characteristics of the inputs and outputs: This includes the instruction space, space for simple variables and fixed-size component variables, space for constants, and so on.
2. A variable part that consists of the space needed by component variable whose size is dependent on the particular problem instance being solved, the space needed by referenced variables and the recursion stack space.

Time Complexity

The time complexity of an algorithm is the amount of computer time it needs to run the program for its completion. The complexity of an algorithm is given by the number of steps taken by the algorithm to compute the function it was written for. The number of steps itself a function of the instance characteristics. Although any specification instance may have several characteristics, the number of steps is computed as a function of some subset of these. Usually, we choose those characteristics that are of importance to us. E.g., we might be interested in knowing how the computing time increases as input increases. In this case the no. of steps will be computed as a function of the number of inputs alone. For a different algorithm, we might be interested in determining how the computing time increases as the magnitude of one of the inputs increases. In this case the no. of steps will be computed as a function of the magnitude of this input alone.

There are two kinds of notation that are used to measure the execution time of the algorithms. They are the Algorithmic Notations and Big-O Notation

Algorithmic Notation

An algorithmic notation specifies the various operations and path decisions on data structures. Algorithmic notations are used because they are less cryptic and can be used for other applications and data analysis. The properties of an algorithm are:

1. Every algorithm has a name.
2. It has an introductory comment, which briefly describes the algorithm, the assumptions made and the variables used.
3. It consists of steps and giving the details of the step being carried out.
4. It contains various statements and control structures these steps are executed in a left to right order.

An algorithm can be analyzed in the three ways. They are Worst-case, Average-case Amortized WORST CASE ANALYSIS Worst case analysis studies an algorithm for the maximum possible time it takes to perform an operation. It involves selecting a set of inputs, which can be expanded to any size. The algorithm is run for as long as possible. The inputs may be static or dynamic. Worst-case analysis focuses on inputs of each size that make a program takes the longest time

Big O Notation

One of the popular notations used today is the Big O notation. The Big O notation provides a theoretical measure of the time or memory required by an algorithm. It also enables the user to compare the expected run times.