1. Generality

• Description: Refers to how well an algorithm or system applies to a wide range of problems or input data.
• Example: A sorting algorithm that works for numbers, strings, and complex objects is considered highly general.

2. Determinism

• Description: Describes whether an algorithm consistently produces the same output given the same input.

  a. Strongly Deterministic: The algorithm always produces the same output for the same input, and its internal states or execution path are fully predictable.

  Example: Traditional Merge Sort is strongly deterministic because its behavior is entirely predictable.

  b. Weakly Deterministic: The output remains the same for the same input, but the internal process or order of execution may vary.

  Example: Parallel algorithms may produce consistent results, but the order of operations can differ across executions.

3. Termination

• Description: Describes whether and how an algorithm finishes its execution.

Stochastic Termination: The algorithm terminates based on some probabilistic factors.

Example: Dice Roll Game

Imagine a game where you roll a dice repeatedly, and the process ends when you roll a 6. The termination of this game is stochastic because it relies on a random event (rolling the die).

Steps:

1. Roll a die.
2. If the outcome is 6, stop (terminate).
3. Otherwise, repeat the roll.

Stochastic Nature: The number of rolls required to terminate is unpredictable and varies each time you play, depending on random chance.

Expected Rolls: Statistically, the average number of rolls to get a 6 is 6 (due to the probability of 1/6 per roll), but this is not deterministic—it can happen on the first roll, the tenth roll, or any number of rolls.

4. Correctness

Refers to whether an algorithm produces the correct output.

Partial Correctness