What is Algorithm & How to analyse algo in terms of Space and time complexity

What is an Algorithm ?

An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain predefined task.

Algorithm is not the complete code or program, it is just the core logic(solution) of a problem, which can be expressed either as an informal high level description as pseudocode or using a flowchart.

Every Algorithm must satisfy the following properties:

1. Input- There should be 0 or more inputs supplied externally to the algorithm.
2. Output- There should be atleast 1 output obtained.
3. Definiteness- Every step of the algorithm should be clear and well defined.
4. Finiteness- The algorithm should have finite number of steps.
5. Correctness- Every step of the algorithm must generate a correct output.

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space. The performance of an algorithm is measured on the basis of following properties :

1. Time Complexity
2. Space Complexity

---

Space Complexity

Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of that algorithm Space complexity must be taken seriously for multi-user systems and in situations where limited memory is available.

An algorithm generally requires space for following components :

• Instruction Space : Its the space required to store the executable version of the program. This space is fixed, but varies depending upon the number of lines of code in the program.
• Data Space : Its the space required to store all the constants and variables values
• Environment Space : Its the space required to store the environment information needed to resume the suspended function.

To calculate the space complexity, we must know the memory required to store different data type values (according to the compiler).

 For example, the C Programming Language compiler requires the following...

• 2 bytes to store Integer value,
• 4 bytes to store Floating Point value,
• 1 byte to store Character value,
• 6 (OR) 8 bytes to store double value

Example :

int main()

{

                int a[10] , b,c ;

             }

         

It occupy 10 sequential memory locations it will not check whether we have entered 10 no or not it will hold all memory so space complexity will be  (a[10] + b + c ) so it will be  10 + 1+1= 12

Time Complexity

Time Complexity is a way to represent the amount of time needed by the program to run till its completion. The time complexity is not applicable for declaration part. As a user we cannot judge the amount of clock time require to execute certain instruction. Because it depends on following factors

1.      The 32 bit or 64 bit machine which runs the program

2.      The instruction set/ programming language which executes the instruction

3.      Time require to execute each instruction may be different

4.      Translation of program code to machine code is also takes different amount of time.

5.      It also depends of multiprogramming and distributed or time sharing machine.

These factors affect the execution time on machine to machine. owe cannot predict exact time of execution. Hence the performance of every algorithm will be measured in terms of frequency count.

 Every time it will be depends on the performance of computer. So if we consider time as a measure for algorithm analysis it will not be accurate every time. So we will consider the frequency of the statement that are appearing in program execution.

Example : 1

int main()

{

int a;

a = 7; …………………………………………………..1

cout<<”a”;……………………………………………..1

}

Example 2 :

void function()

{

int a;

a=7;……………………………………………………..1

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

{

a=  a+i;………………………………………………….n

}