The essential criteria that an algorithm must satisfy include correctness, efficiency, clarity, finiteness, and feasibility. Correctness ensures the algorithm produces the desired output for all valid inputs. Efficiency involves optimizing time and space resources, crucial for performance and scalability. Clarity makes the algorithm understandable, facilitating maintenance and collaboration. Finiteness guarantees that the algorithm will eventually terminate, avoiding infinite loops. Feasibility ensures the algorithm can practically solve the problem given constraints like available time and computational resources. These criteria are vital because they ensure an algorithm is functional, performs well, is maintainable, concludes execution appropriately, and is practical for real-world applications.

The substitution method involves guessing the form of the solution and using mathematical induction to prove the guess correct. For T(n)=T(n-2)+n^2, assume the solution form T(n) = Cn^3 for some constant C. Establish the base case by calculating T(n) for small n to find a corresponding C value. Substitute back into the recurrence to verify the hypothesized solution holds for all n by showing that replacing T(n-2) with its conjectured form results in an inequality or equality that supports the hypothesized solution. This process systematically replaces recursive terms, turning the recurrence into a closed form.

Applying the master method to T(n)=9T(n/3)+n, identify a=9, b=3, and f(n)=n. Compute n^log_b(a) = n^log_3(9) = n^2. Since f(n)=n=O(n^2/e), satisfying f(n) = O(n^c) for c < log_b(a), the recurrence fits Case 1 of the master theorem, resulting in T(n) = Θ(n^2). The master method concludes by comparing f(n) to n^log_b(a) and determining dominance; here, the function grows slower than n^log_b(a), therefore, T(n) equates to the more dominant term.

In terms of asymptotic (big-O) complexity, n^n is the most computationally complex function. This is due to the exponential base being the variable itself, resulting in faster growth as n increases compared to fixed exponential bases like 2^n or (1.000001)^n, and compounded polynomials like n^10 * 2^(n/2). n^n grows significantly faster because for any n, n^n involves multiplying n n-times, exceeding the growth of other functions where a fixed base is raised to a power of n.

To apply the 0/1 Knapsack algorithm with items having respective profits (10, 40, 30, 50) and weights (5, 4, 6, 3) with capacity W=10, we build a dynamic programming table. Initialize a table K[n][w] where n is the number of items and w is the weight capacity. Each entry K[i][j] captures the maximum profit using items 1 through i and total weight capacity j. For i=1, using item 2 (profit 40, weight 4), K[1][4] = 40. Continuing, K[2][10] = 50 from item 4 plus 40 from item 2. The maximum achievable profit is 90 by selecting items 2 (weight 4) and item 4 (weight 3).

The greedy approach constructs a solution piece by piece by selecting the local optimum choice at each step, which decisions are made in hopes of finding a global optimum. Key characteristics include: making a choice based on available information without concerning future outcomes, the non-reversal of decisions, and step-by-step problem solving by optimizing locally hoping it leads to a global solution. Greedy methods work where local optima form a global optimum, such as in algorithms like Huffman encoding or Dijkstra's shortest path. For example, in the fractional knapsack problem, the greedy strategy involves selecting items based on maximum value/weight ratio until the knapsack's capacity is filled.

Prim's algorithm builds the MST by starting from an arbitrary node and growing the MST one edge at a time, choosing the smallest weight edge from the vertices already in the MST. It is implemented using priority queues. In contrast, Kruskal's algorithm sorts all edges by weight and adds them one-by-one to the MST, provided they don't form a cycle, using a union-find data structure. For example, consider a graph with vertices V1-V4 and edges (V1-V2), (V2-V3), (V3-V4), and (V1-V4) with respective weights 1, 2, 2, and 3. Prim's would start at V1, add V2 (weight 1), then V3 (weight 2), and finally V4 (weight 2), constructing the MST in a queue-managed manner. Kruskal's algorithm would start by selecting the smallest edge V1-V2, then V2-V3, and finally V3-V4, based on sorting edge weights, to ensure no cycles are formed.