Elementary Properties of Algorithm, Need for Algorithm, and RAM Model Analysis

Elementary Properties of Algorithm

An algorithm is a finite set of well-defined instructions to solve a specific problem in a finite amount of time.

Every algorithm must satisfy the following elementary properties:

• Finiteness — An algorithm must always terminate after a finite number of steps. It cannot run indefinitely.

• Definiteness — Each step of the algorithm must be precisely and unambiguously defined. There should be no confusion about what action to perform.

• Input — An algorithm has zero or more inputs taken from a specified set of objects.

• Output — An algorithm has one or more outputs that have a specific relation to the inputs.

• Effectiveness — Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. Each operation must be feasible.

• Generality — The algorithm should work for all instances of the problem, not just a particular input.

• Independence — An algorithm should be independent of any programming language; it is a logical step-by-step solution.

---

Why Do We Need Algorithms?

• Problem Solving — Algorithms provide a systematic and logical approach to solve complex problems step by step.

• Efficiency — They help us find the most efficient solution in terms of time and space among multiple possible solutions.

• Correctness — A well-designed algorithm guarantees that the correct output is produced for every valid input.

• Communication — Algorithms serve as a clear way to communicate the solution approach to other programmers or stakeholders.

• Scalability — They help us predict how a solution will perform when input size grows large.

• Reusability — Once designed, an algorithm can be implemented in any programming language and reused across projects.

• Comparison — Algorithms allow us to compare different solutions to the same problem and pick the best one.

---

Analysis of the RAM Model for Analysis of Algorithm

The RAM (Random Access Machine) model is a theoretical model of computation where each simple operation (+, −, ×, ÷, comparison, assignment, memory access) takes exactly one unit of time, and each memory access also takes one unit of time.

Key Assumptions of the RAM Model:

• Each simple operation (addition, subtraction, multiplication, division, comparison, assignment) takes 1 step.
• Each memory read/write takes 1 step.
• Instructions are executed sequentially (one after another).
• Memory is unlimited and access to any memory location takes constant time (random access).
• No concurrent/parallel operations are considered.

Why RAM Model is Used:

• It provides a machine-independent framework to analyze algorithms.
• It allows us to count the number of basic operations as a function of input size $n$.
• It simplifies analysis by ignoring hardware-specific details.

Example — Linear Search Analysis using RAM Model:

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {    // comparison + increment each iteration
        if (arr[i] == key)            // memory access + comparison
            return i;                 // 1 step
    }
    return -1;                        // 1 step
}

Counting steps using RAM model:

Operation	Cost	Frequency (Worst Case)
i = 0 (assignment)	1	1
i < n (comparison)	1	n + 1
i++ (increment)	1	n
arr[i] == key (access + compare)	2	n
return -1	1	1

Total steps (Worst Case): $1 + (n+1) + n + 2n + 1 = 4n + 3$

So, in the RAM model, the time complexity of linear search is $T(n) = 4n + 3 = O(n)$.

• Best Case: Element found at first position → $O(1)$
• Worst Case: Element not found → $O(n)$
• Average Case: Element found at middle → $O(n/2) = O(n)$

---

Conclusion

The elementary properties ensure an algorithm is correct and practical. The need for algorithms arises from the demand for efficient, correct, and scalable solutions. The RAM model provides a simple yet powerful abstraction to analyze algorithm performance by counting basic operations, independent of actual hardware, making it the standard model for theoretical algorithm analysis.