Algorithm

An algorithm is a finite, ordered sequence of clear and unambiguous steps used to solve a particular problem or perform a specific task.

In simple words:

An algorithm is a step-by-step procedure for solving a problem and producing the required output from given input.

Example: Algorithm for Finding the Largest of Two Numbers

Step 1: Start

Step 2: Read A and B

Step 3: Compare A and B

Step 4: If A > B, display A

       otherwise display B

Step 5: Stop

2.Characteristics of 

A good algorithm should satisfy the following five fundamental criteria

1: Input-An algorithm should have zero or more clearly specified inputs.

2: Output- An algorithm should produce at least one clearly defined output.

3: Definiteness-Every step must be clear, precise and unambiguous.

4: Finiteness-The algorithm must terminate after a finite number of steps.

5: Effectiveness-Every operation must be simple, executable and practically feasible in a finite amount of time.

Example- For finding the sum of two numbers:

Input:       A, B

Process:     Add A and B

Output:      Sum

Definiteness: Addition operation is clearly specified

Finiteness:  Algorithm terminates after a fixed number of steps

Effectiveness: Addition can be performed by the computer

3. Algorithm Design

Algorithm design is the process of developing a systematic sequence of steps to solve a computational problem correctly and efficiently.

General Algorithm Design Process

Problem Definition

       ↓

Problem Analysis

       ↓

Identify Input and Output

       ↓

Select Data Structures

       ↓

Select Algorithmic Technique

       ↓

Develop Algorithm

       ↓

Verify Correctness

       ↓

Analyze Time and Space

       ↓

Implement

       ↓

Test and Optimize

Common Algorithm Design Techniques

• Brute Force -Try all possible solutions :Linear Search

• Divide and Conquer -Divide problem into smaller subproblems :Merge Sort, Quick Sort

• Greedy-Select the locally best option: Kruskal's Algorithm

• Dynamic Programming- Store solutions of overlapping subproblems : 0/1 Knapsack

• Backtracking- Build solution and backtrack when necessary : N-Queens

• Recursion-Function solves smaller versions of itself :Factorial, Tree Traversal

4. Algorithm Analysis

Algorithm analysis is the process of determining the efficiency and resource requirements of an algorithm.

The two main resources are:

1. Time Complexity

Measures how the execution time grows with input size.

Examples:

O(1)       Constant

O(log n)   Logarithmic

O(n)       Linear

O(n log n) Linearithmic

O(n²)      Quadratic

O(2ⁿ)      Exponential

2. Space Complexity

Measures the amount of memory required by an algorithm as the input size increases.

5. Best Case, Worst Case and Average Case

The performance of an algorithm may depend on the particular input. Therefore, we analyze different cases.

A. Best Case

The best case is the input condition under which an algorithm performs the minimum number of operations or takes the minimum time.

Example: Linear Search

Array: 10  20  30  40  50

Search for: 10

The element is found at the first position.Therefore: Best Case = O(1)

B. Worst Case

The worst case is the input condition under which an algorithm performs the maximum number of operations or takes the maximum time.

For linear search, if we search for 50:

10 → 20 → 30 → 40 → 50

All five elements must be examined.

Therefore:

Worst Case = O(n)

If the element is not present, the algorithm may also need to examine all n elements.

C. Average Case

The average case represents the expected performance of an algorithm over a suitable distribution of possible inputs.

For linear search, assuming the searched element is equally likely to occur at any position:

Comparisons ≈ (n + 1) / 2

Therefore, asymptotically:

Average Case = O(n)

6. Comparison

Best Case : Minimum work O(1)

Average Case: Expected/typical work O(n)

Worst Case: Maximum work O(n)

Conceptual Representation

               Algorithm Analysis

                       │

             ┌─────────┴─────────┐

             │                  │

        Time Complexity     Space Complexity

                   │

         ┌─────┼─────┐

           │     │    │

     Best Average Worst

     Case  Case   Case

Key Point

Best case tells us the minimum computational cost, worst case tells us the maximum computational cost, and average case estimates the expected computational cost for typical inputs.

For Data Structures, algorithm analysis is especially important because the choice of data structure directly affects the time and space complexity of operations such as searching, insertion, deletion and traversal.