Optimal solution:
An optimal solution is a solution to a problem that gives the best possible result among all feasible solutions. Depending on the problem, this means either minimum cost or maximum profit, and no other valid solution can do better than it.

Does greedy algorithm always guarantee optimal solution?

No, the greedy algorithm does not always guarantee an optimal solution.

A greedy algorithm makes the best possible choice at each step (locally optimal choice) with the hope of finding a global optimum. However, this strategy does not always lead to the best overall solution.

Greedy works correctly only when the problem has:

1. Greedy choice property (local choice leads to global optimum)

2. Optimal substructure (optimal solution contains optimal subsolutions)

When greedy gives optimal solution:

• Fractional Knapsack

• Activity Selection Problem

• Huffman Coding

• Minimum Spanning Tree (Prim’s, Kruskal’s)

• Dijkstra’s algorithm (non-negative weights)

When greedy fails:

• 0/1 Knapsack

• Coin change (in some cases)

• Some scheduling problems with constraints

Conclusion:
Greedy algorithm is efficient and simple, but it does not always guarantee an optimal solution unless the problem satisfies specific mathematical properties.

Best and Worst Case of Bubble Sort:

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass, the largest element moves to its correct position.

Best Case:

Condition:
The array is already sorted.

Example: [1, 2, 3, 4, 5]

If optimized Bubble Sort is used (with a swap flag), the algorithm detects no swaps in the first pass and stops early.

Time Complexity:
O(n)

Reason:
Only one pass is needed to confirm the array is sorted, and no swaps occur.

Space Complexity:
O(1)

Worst Case:

Condition:
The array is in reverse order.

Example: [5, 4, 3, 2, 1]

Every element needs to be swapped in every pass.

Time Complexity:
O(n²)

Reason:

• First pass: n−1 comparisons

• Second pass: n−2 comparisons

• ...
  Total comparisons ≈ n(n−1)/2

Space Complexity:
O(1)

Final Summary:

Best case:

• Time: O(n)

• Condition: Already sorted array

Worst case:

• Time: O(n²)

• Condition: Reverse sorted array

Class P:
Class P is the set of decision problems that can be solved in polynomial time by a deterministic algorithm.
These are problems for which an algorithm exists whose running time is bounded by a polynomial function of the input size.
Example: sorting, shortest path, minimum spanning tree.

Class NP:
Class NP is the set of decision problems for which a given solution can be verified in polynomial time by a deterministic algorithm.
This means that if someone provides a candidate solution, we can check whether it is correct efficiently (in polynomial time), even if finding the solution may be hard.
Example: satisfiability problem (SAT), Hamiltonian path, subset sum.

Why do we need approximation algorithms (Justification):

Many real-world optimization problems are NP-Hard, meaning:

• No known polynomial-time algorithm exists to solve them exactly

• Exact solutions become infeasible for large inputs due to exponential time complexity

In such cases, approximation algorithms are used to:

1. Get near-optimal solutions in reasonable time
   Instead of waiting exponential time for exact answers, we accept solutions that are “close enough”.

2. Handle NP-hard optimization problems
   Problems like Traveling Salesman Problem, Knapsack (0/1), Vertex Cover cannot be solved exactly in polynomial time (unless P = NP).

3. Trade-off between accuracy and efficiency
   Approximation algorithms provide a balance between solution quality and computation time.

4. Practical usefulness
   In real applications (networks, scheduling, logistics), an almost optimal solution is often sufficient.

Conclusion:
Class P contains efficiently solvable problems, NP contains efficiently verifiable problems, and approximation algorithms are needed because many important NP-hard problems cannot be solved exactly in polynomial time, so we settle for near-optimal efficient solutions.

Worst case of Binary Search:

Binary search works on a sorted array by repeatedly dividing the search space into two halves.

Worst case occurs when:

• The element is not present in the array, or

• The element is found at the deepest level of the recursion/iteration tree.

At each step, the array size reduces as:
n → n/2 → n/4 → n/8 → ... → 1

So the maximum number of comparisons required is:
log₂(n)

Therefore, worst case time complexity is:
O(log n)

Justification:
Even in the worst case, binary search eliminates half of the remaining elements at each step, so the number of steps grows logarithmically with input size.

Edit Distance (Dynamic Programming):

Given:
String 1: RELEVANT (length = 8)
String 2: ELEPHANT (length = 8)

We define:
dp[i][j] = minimum number of operations to convert first i characters of string1 into first j characters of string2.

Allowed operations:

• Insert

• Delete

• Replace

Step 1: Initialize

If i = 0 → dp[0][j] = j
If j = 0 → dp[i][0] = i

Step 2: Recurrence

If characters match:
dp[i][j] = dp[i-1][j-1]

Else:
dp[i][j] = 1 + min(
dp[i-1][j], // delete
dp[i][j-1], // insert
dp[i-1][j-1] // replace
)

Step 3: Final DP result

After filling the table for:
"RELEVANT" → "ELEPHANT"

The computed edit distance is:

Minimum edit distance = 4

Final Answer:

Worst case of Binary Search:
O(log n)

Edit Distance between "RELEVANT" and "ELEPHANT":

Worst case of Binary Search:

Binary search works on a sorted array by repeatedly dividing the search space into two halves.

Worst case occurs when:

• The element is not present in the array, or

• The element is found at the deepest level of the recursion/iteration tree.

At each step, the array size reduces as:
n → n/2 → n/4 → n/8 → ... → 1

So the maximum number of comparisons required is:
log₂(n)

Therefore, worst case time complexity is:
O(log n)

Justification:
Even in the worst case, binary search eliminates half of the remaining elements at each step, so the number of steps grows logarithmically with input size.

Edit Distance Question: