Algorithm in Data Structure | learn tut

 

What is an Algorithm?

An algorithm is a process or a set of rules required to perform calculations or some other problem-solving operations especially by a computer.

It contains the finite set of instructions which are being carried in a specific order to perform the specific task. It is not the complete program or code; it is just a solution (logic) of a problem, which can be represented either as an informal description using a Flowchart or Pseudocode.

 

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 at least 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

 

Factors of an Algorithm

The following are the factors that we need to consider for designing an algorithm:

• Modularity: If any problem is given and we can break that problem into small-small modules or small-small steps, which is a basic definition of an algorithm, it means that this feature has been perfectly designed for the algorithm.
• Correctness: The correctness of an algorithm is defined as when the given inputs produce the desired output, which means that the algorithm has been designed algorithm. The analysis of an algorithm has been done correctly.
• Maintainability: Here, maintainability means that the algorithm should be designed in a very simple structured way so that when we redefine the algorithm, no major change will be done in the algorithm.
• Functionality: It considers various logical steps to solve the real-world problem.
• Robustness: Robustness means that how an algorithm can clearly define our problem.
• User-friendly: If the algorithm is not user-friendly, then the designer will not be able to explain it to the programmer.
• Simplicity: If the algorithm is simple then it is easy to understand.
• Extensibility: If any other algorithm designer or programmer wants to use your algorithm then it should be extensible.

 

Dataflow of an Algorithm

• Problem: A problem can be a real-world problem or any instance from the real-world problem for which we need to create a program or the set of instructions. The set of instructions is known as an algorithm.
• Algorithm: An algorithm will be designed for a problem which is a step by step procedure.
• Input: After designing an algorithm, the required and the desired inputs are provided to the algorithm.
• Processing unit: The input will be given to the processing unit, and the processing unit will produce the desired output.
• Output: The output is the outcome or the result of the program.

 

 

Now we will look an example of an algorithm in programming.

We will write an algorithm to add two numbers entered by the user.

 

The following are the steps required to add two numbers entered by the user:

Step 1: Start

Step 2: Declare three variables a, b, and sum.

Step 3: Enter the values of a and b.

Step 4: Add the values of a and b and store the result in the sum variable, i.e., sum=a+b.

Step 5: Print sum

Step 6: Stop

 

Asymptotic Analysis

Asymptotic analysis is the process of calculating the running time of an algorithm in mathematical units to find the program’s limitations, or “run-time performance.” The goal is to determine the best case, worst case and average case time required to execute a given task.

 

While run-time performance can be calculated with many different functions, the limiting behavior of the algorithm is expressed graphically using simple notation:

• Ο(n): Is the upper bound of an algorithm's running time and measures the worst-case scenario of how long an algorithm can possibly take to complete a given operation.
• Ω(n): Is the lower bound of an algorithm's running time and measures the best-case scenario of how long an algorithm can possibly take to complete a given operation.
• Θ(n): Is charting both the upper and lower running time boundaries, with the average case scenario express as the average between each border.

 

the time required by an algorithm comes under three types:

Worst case: It defines the input for which the algorithm takes a huge time.

Average case: It takes average time for the program execution.

Best case: It defines the input for which the algorithm takes the lowest time.

 

Asymptotic Notations

The commonly used asymptotic notations used for calculating the running time complexity of an algorithm is given below:

• Big oh Notation (O)
• Omega Notation (Ω)
• Theta Notation (θ)

 

Big oh Notation (O)

Big O Notation is a mathematical function used in computer science to describe an algorithm’s complexity. It is usually a measure of the runtime required for an algorithm’s execution.

This notation provides an upper bound on a function which ensures that the function never grows faster than the upper bound. So, it gives the least upper bound on a function so that the function never grows faster than this upper bound.

 

It measures the worst case of time complexity or the algorithm's longest amount of time to complete its operation. It is represented as shown below:

Omega Notation (Ω)

It basically describes the best-case scenario which is opposite to the big O notation.

It is the formal way to represent the lower bound of an algorithm's running time. It measures the best amount of time an algorithm can possibly take to complete or the best-case time complexity.

It determines what is the fastest time that an algorithm can run. An algorithm takes at least certain amount of time without using an upper bound, we use big- Ω notation. It is used to bound the growth of running time for large input size.