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

Characteristics of  ALGORITHMS

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: The addition operation is clearly specified

Finiteness:  Algorithm terminates after a fixed number of steps

Effectiveness: Addition can be performed by the computer

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

General Algorithm Design Process

1. Problem Definition

      ↓

2. Problem Analysis

       ↓

3. Identify Input and Output

       ↓

4. Select Data Structures

       ↓

5. Select Algorithmic Technique

       ↓

6. Develop Algorithm

       ↓

7. Verify Correctness

       ↓

8. Analyze Time and Space

       ↓

9. Implement

       ↓

10. 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

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

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

Space Complexity

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

Analysis based on input  or pattern of data 

The performance of an algorithm may depend on the particular input. Therefore, we analyze different cases.  Best Case, Worst Case, and Average Case

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). In other words, 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)

Comparison of Best Case, Average Case, and Worst Case.

Best Case : Minimum work O(1)

Average Case: Expected/typical work O(n)

Worst Case : Maximum work O(n)

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.