Introduction and Asymptotic Analysis

Introduction

Data structures and algorithms lay down the foundation of computational problem-solving. To design efficient computer programs, it is necessary to choose the appropriate data structures and design their algorithms accordingly.

Algorithms

An algorithm is a finite set of unambiguous steps or instructions to solve a given problem. Knowledge of algorithms helps us to get desired results faster by applying the appropriate algorithm in appropriate situations. With experience, it becomes easy to solve new problems. By looking into various problem-solving algorithms or techniques, we begin to develop a pattern that will help us in solving similar problems.

The properties of an algorithm are as follows:

1. It takes zero or more inputs.

2. It should produce one or more output.

3. It should be deterministic. It produces the same output if the same input is provided again.

4. It should be correct. It should be correct and able to process all the given inputs and provide the correct output.

5. It should terminate in a finite time.

6. It should be efficient. The algorithm should be quick and optimized in solving problems. The algorithm should be efficient in solving problems.

The complexity of an algorithm is the amount of time or space required by the algorithm to process the input and produce the output.

There are two types of complexity:

• Time complexity: The time required by an algorithm to produce output for an input of size ‘n’. It is represented by the function T(n), time required per the input size n.

Lesser the time complexity, more efficient will be the algorithm.

• Space complexity: The memory that an algorithm is going to consume to produce output for an input of size ‘n’. It is represented by the function S(n), memory used per the input size n.

Asymptotic analysis or asymptotic notations

Asymptotic analysis or asymptotic notation is used to compare the efficiency of algorithms independent of any dataset. We are generally interested in the order of growth of an algorithm, and not interested in the exact time required for running an algorithm. This time is also called asymptotic running time.