Software Engineering basics - Algorithm

 What is an Algorithm?

An algorithm is a step-by-step procedure or a set of rules designed to perform a specific task or solve a problem. In computer science, algorithms are the backbone of programming and software development.

Definition:
An algorithm is a finite, well-defined, and ordered set of instructions that takes input(s), processes them, and produces output(s) to solve a particular problem.

 Key Characteristics of an Algorithm:

  1. Input: Zero or more inputs

  2. Output: At least one output

  3. Definiteness: Clear and unambiguous steps

  4. Finiteness: Must terminate after a finite number of steps

  5. Effectiveness: Steps should be basic enough to be carried out

 What is Euclid's Algorithm?

Euclid's Algorithm is an ancient and efficient method for computing the Greatest Common Divisor (GCD) of two integers. The GCD is the largest number that divides both numbers without leaving a remainder.

Euclid’s Algorithm Logic (Using Subtraction or Modulus):

Let’s say you want to find GCD(a, b):

  • Step 1: If b = 0, then GCD(a, b) = a

  • Step 2: Otherwise, compute GCD(b, a % b)

Repeat until b becomes 0.

Euclid’s Algorithm (Using Modulo) – Pseudocode:

function gcd(a, b)
    while b ≠ 0
        temp ← b
        b ← a mod b
        a ← temp
    return a

 Example:

Find GCD(48, 18)

Step 1: 48 mod 18 = 12  → GCD(18, 12)
Step 2: 18 mod 12 = 6   → GCD(12, 6)
Step 3: 12 mod 6 = 0    → GCD(6, 0)

Answer: GCD = 6

⏱ Time Complexity:

  • Time Complexity: O(log min(a, b))

  • Space Complexity: O(1) (iterative version)