Data Structures and Algorithms Tutorials | IT Developer
IT Developer

Data Structures & Algorithms - Character of Algorithms

Share with a Friend
Previous
HOME
Next

Characteristics of an Algorithm

An algorithm is a step-by-step procedure to solve a problem efficiently. For a process to be considered an algorithm, it must have the following characteristics:

1. Well-Defined Inputs

  • An algorithm must have zero or more well-defined inputs.
  • The inputs must be clearly specified.

🔹 Example:
For an algorithm that finds the sum of two numbers, inputs should be two numbers.

C C++ Java Python 
#include <stdio.h>


int add(int a, int b) {

       return a + b;

   }



int main() {

       int x = 5, y = 10;

       printf("Sum: %d\n", add(x, y)); // Output: Sum: 15

       return 0;

}

Output

Sum: 15

#include <iostream>
using namespace std;


int add(int a, int b) {

 return a + b;
}


int main() {

   int x = 5, y = 10;

   cout << "Sum: " << add(x, y) << endl; // Output: Sum: 15

   return 0;

}

Output

Sum: 15

class Sum {

 public static int add(int a, int b) {

      return a + b;

   }

    

     public static void main(String[] args) {

          int x = 5, y = 10;

          System.out.println("Sum: " + add(x, y)); // Output: Sum: 15

        }

  }

Output

Sum: 15

def add(a, b):

    return a + b


print("Sum:", add(5, 10)) # Output: Sum: 15

Output

Sum: 15

✅ Valid Inputs → (5,10) valid output (15).
❌ Invalid Inputs → ("hello", 5) (not well-defined)

2. Well-Defined Outputs

An algorithm must provide a clear and correct output for given inputs.

  • An algorithm must produce at least one valid output.
  • The output should be clearly related to the input.

🔹 Example: Find the Maximum of Two Numbers

  • Input: Two integers
  • Output: The larger number
C C++ Java Python 


#include <stdio.h>


int max(int a, int b) {

    return (a > b) ? a : b;

}



int main() {

    printf("Max: %d\n", max(5, 10)); // Output: Max: 10

    return 0;

}

Output

Max: 10



#include <iostream>

using namespace std;



int max(int a, int b) {

    return (a > b) ? a : b;

}



int main() {

    int x = 10, y = 20;

    cout << "Maximum: " << max(x, y) << endl; // Output: Maximum: 20

    return 0;
}

Output

Maximum: 20



class MaxNumber {
 
    public static int max(int a, int b) {
 
        return (a > b) ? a : b;
 
   }
 
 

public static void main(String[] args) {
 
     int x = 10, y = 20;
 
     System.out.println("Maximum: " + max(x, y)); // Output: Maximum: 20
 
   }

}

Output

Maximum: 20



def max_of_two(a, b):
 
    return max(a, b)



x, y = 10, 20

print("Maximum:", max_of_two(x, y)) # Output: Maximum: 20

Output

Maximum: 20


✅ The algorithm returns a correct and expected output.

 

💡 Explanation

  • We compare two numbers a and b.
  • Use the ternary operator (? :) in C, C++ & Java.
  • Use the built-in max() function in Python.

🔹 Example:
For a sorting algorithm, the output should be a sorted list.

Python

def sort_numbers(arr): 

    return sorted(arr) 
 
print(sort_numbers([5, 2, 9, 1]))  # Output: [1, 2, 5, 9]

✅ Valid Output → Sorted List
❌ Invalid Output → Unsorted or incorrect list

3. Finiteness (Must Terminate)

An algorithm must terminate after a finite number of steps.

🔹 Example: Compute Factorial of a Number (Recursive vs. Infinite Loop)

  • An algorithm must terminate after a finite number of steps.
  • It should not run indefinitely.

🔹 Example (Factorial Algorithm – Correct):

C C++ Java Python 
#include <stdio.h>



long long factorial(int n) {

   if (n == 0 || n == 1)

       return 1;

   return n * factorial(n - 1);

}



int main() {

    int num = 5;

    printf("Factorial of %d is %lld\n", num, factorial(num)); // Output: 120

    return 0;

}

Output

Factorial of 5 is 120

#include <iostream>

using namespace std;



long long factorial(int n) {

    if (n == 0 || n == 1)

       return 1;

    return n * factorial(n - 1);

 }



int main() {

   int num = 5;

   cout << "Factorial of " << num << " is " << factorial(num) << endl; // Output: 120

   return 0;

}

Output

Factorial of 5 is 120



class Factorial {

   public static long factorial(int n) {

      if (n == 0 || n == 1)

         return 1;

      return n * factorial(n - 1);

    }



   public static void main(String[] args) {

       int num = 5;

       System.out.println("Factorial of " + num + " is " + factorial(num)); // Output: 120

    }

}

Output

Factorial of 5 is 120



def factorial(n):
 
    return 1 if n == 0 or n == 1 else n * factorial(n - 1)



num = 5

print("Factorial of", num, "is", factorial(num)) # Output: 120

Output

Factorial of 5 is 120

✅ Terminates after a finite number of recursive calls.

 

❌ Incorrect Example (Infinite Loop):

Python

def infinite_loop(n):

 while n > 0:

  print(n) # No termination condition



infinite_loop(5) # Runs forever!

⚠️ This will never stop!

4. Definiteness (Clear Steps)

Each step must be precise and well-defined.

  • Input: An integer
  • Output: "Even" or "Odd"

🔹 Example: Check if a Number is Even or Odd

  • Each step in an algorithm must be clear and unambiguous.
  • The steps should be precisely defined.
C C++ Java Python 
#include <stdio.h>



void check_even_odd(int num) {
 
    if (num % 2 == 0)
 
       printf("%d is Even\n", num);
 
    else
 
       printf("%d is Odd\n", num);

}



int main() {
 
    int num = 7;
 
    check_even_odd(num); // Output: 7 is Odd
 
    return 0;

}

Output

7 is Odd

#include <iostream>

    using namespace std;



void check_even_odd(int num) {
 
    if (num % 2 == 0)
 
       cout << num << " is Even" << endl;
 
    else
 
       cout << num << " is Odd" << endl;

}



int main() {
 
    int num = 7;
 
    check_even_odd(num); // Output: 7 is Odd
 
    return 0;

}

Output

7 is Odd

class EvenOdd {
 
    public static void checkEvenOdd(int num) {
 
        if (num % 2 == 0)
 
           System.out.println(num + " is Even");
 
        else
 
           System.out.println(num + " is Odd");
 
    }



  public static void main(String[] args) {
 
       int num = 7;
 
       checkEvenOdd(num); // Output: 7 is Odd
 
    }

}

Output

7 is Odd

def check_even_odd(num):
 
    print(f"{num} is Even" if num % 2 == 0 else f"{num} is Odd")



num = 7

check_even_odd(num) # Output: 7 is Odd

Output

7 is Odd

✅ The steps are clear and unambiguous.

 

❌ Incorrect Example (Ambiguous Condition):

Python

def max_of_two(a, b): 

    if a is greater than b:  # Incorrect syntax 

        return a 

    else: 
        return b

⚠️ "is greater than" is not a valid syntax → This will cause errors!

5. Effectiveness (Basic Computable Operations)

All operations must be simple enough to execute.

  • The operations in an algorithm must be simple enough to be executed.
  • Every step should be computable in finite time.

🔹 Example: Multiply Two Numbers

C C++ Java Python 
#include <stdio.h>



int multiply(int a, int b) {
 
    return a * b;

}



int main() {
 
    int x, y;
 
    printf("Enter two numbers: ");
 
    scanf("%d %d", &x, &y);
 
    printf("Product: %d\n", multiply(x, y));
 
    return 0;

}

Output

Enter two numbers: 5 10

Product: 50


#include <iostream>

    using namespace std;



int multiply(int a, int b) {
 
    return a * b;

}



int main() {
 
    int x, y;
 
    cout << "Enter two numbers: ";
 
    cin >> x >> y;
 
    cout << "Product: " << multiply(x, y) << endl;
 
    return 0;

}

Output

Enter two numbers: 5 10

Product: 50


import java.util.Scanner;


class MultiplyNumbers {
 
    public static int multiply(int a, int b) {
 
    return a * b;
 
}
 
 

public static void main(String[] args) {
 
      Scanner scanner = new Scanner(System.in);
 
      System.out.print("Enter two numbers: ");
 
      int x = scanner.nextInt();
 
      int y = scanner.nextInt();
 
      System.out.println("Product: " + multiply(x, y));
 
      scanner.close();
 
   }

}

Output

Enter two numbers: 5 10

Product: 50


def multiply(a, b):
 
    return a * b



x, y = map(int, input("Enter two numbers: ").split())

print("Product:", multiply(x, y))

Output

Enter two numbers: 5 10

Product: 50

✅ Effective operations: Multiplication is a basic operation.

6. Language Independence

An algorithm must be independent of any programming language.

  • An algorithm should be independent of programming languages.
  • It should be expressed in natural language or pseudocode.

🔹 Example (Finding the Square of a Number – Pseudocode):

Algorithm

Algorithm SquareNumber(N)


    

  1. Start
    2. 

  2. Multiply N by N
    3. 

  3. Return Result
    4. 

  4. Stop
    5.

✅ Can be implemented in any programming language:

C C++ Java Python 
#include <stdio.h>



int square(int num) {
 
    return num * num;

}



int main() {
 
    int num;
 
    printf("Enter a number: ");
 
    scanf("%d", &num);
 
    printf("Square of %d is %d\n", num, square(num));
 
    return 0;

}

Output

Enter a number: 5

Square of 5 is 25


#include <iostream>

using namespace std;



int square(int num) {
 
    return num * num;

}



int main() {
 
    int num;
 
    cout << "Enter a number: ";
 
    cin >> num;
 
    cout << "Square of " << num << " is " << square(num) << endl;
 
    return 0;

}

Output

Enter a number: 5

Square of 5 is 25


import java.util.Scanner;


class SquareNumber {
 
    public static int square(int num) {
 
    return num * num;
 
}



public static void main(String[] args) {
 
    Scanner scanner = new Scanner(System.in);
 
    System.out.print("Enter a number: ");
 
    int num = scanner.nextInt();
 
    System.out.println("Square of " + num + " is " + square(num));
 
    scanner.close();
 
}
}

Output

Enter a number: 5

Square of 5 is 25


def square(num):
 
    return num * num



num = int(input("Enter a number: "))

print("Square of", num, "is", square(num))

Output

Enter a number: 5

Square of 5 is 25

✅ The logic remains the same across languages!

7. Input Size Independence

The algorithm must work for any valid input size.

  • An algorithm must work for any valid input size (including edge cases).
  • It should not be restricted to specific inputs.

💡 Why Use Dynamic Programming?

Recursive Fibonacci (O(2^n)) is slow due to repeated calculations.
Dynamic Programming (DP) stores previously computed values to optimize performance, reducing time complexity to O(n).

🔹 Example: Finding Fibonacci Number (Works for Large Inputs)

C C++ Java Python 
#include <stdio.h>



int fibonacci(int n) {
 
    int dp[n + 1]; // Array to store computed values
 
    dp[0] = 0, dp[1] = 1;
 
 
    for (int i = 2; i <= n; i++)
 
         dp[i] = dp[i - 1] + dp[i - 2];

    
return dp[n];

}



int main() {
 
    int n;
 
    printf("Enter a number: ");
 
    scanf("%d", &n);
 
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
 
    return 0;

}

Output

Enter a number: 6
Fibonacci(6) = 8


#include <iostream>

using namespace std;



int fibonacci(int n) {
 
    int dp[n + 1];
 
    dp[0] = 0, dp[1] = 1;
 
 
    for (int i = 2; i <= n; i++)
 
        dp[i] = dp[i - 1] + dp[i - 2];

    
return dp[n];

}



int main() {
 
    int n;
 
    cout << "Enter a number: ";
 
    cin >> n;
 
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
 
    return 0;

}

Output

Enter a number: 6
Fibonacci(6) = 8


import java.util.Scanner;


class FibonacciDP {
 
    public static int fibonacci(int n) {
 
    int[] dp = new int[n + 1];
 
    dp[0] = 0;
 
    dp[1] = 1;

    
for (int i = 2; i <= n; i++)
 
        dp[i] = dp[i - 1] + dp[i - 2];

    
return dp[n];
 
}



public static void main(String[] args) {
 
     Scanner scanner = new Scanner(System.in);
 
     System.out.print("Enter a number: ");
 
     int n = scanner.nextInt();
 
     System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
 
     scanner.close();
 
   }

}

Output

Enter a number: 6
Fibonacci(6) = 8


def fibonacci(n):
 
    dp = [0] * (n + 1)
 
    dp[0], dp[1] = 0, 1
 
 
    for i in range(2, n + 1):
 
    dp[i] = dp[i - 1] + dp[i - 2]

    
return dp[n]



n = int(input("Enter a number: "))

print(f"Fibonacci({n}) =", fibonacci(n))

Output

Enter a number: 6
Fibonacci(6) = 8

8. Optimality (Efficient Use of Resources)

The algorithm should be optimized for time and space.

  • An algorithm should be efficient in terms of time and space.
  • The best algorithm uses less memory and fewer steps.

🔹 Example: Optimized vs. Naïve Fibonacci

❌ Naïve Recursive Approach (Inefficient)

🔹 Example (Efficient Fibonacci using Dynamic Programming):

Python

def fib(n, dp={}): 

    if n <= 1: 

        return n 

    if n not in dp: 

        dp[n] = fib(n - 1, dp) + fib(n - 2, dp) 

    return dp[n] 
 
print(fib(10))  # Output: 55

✅ Optimized using memoization (stores results to avoid recomputation).

❌ Inefficient Example (Exponential Recursion):

Python

def fib(n): 

    if n <= 1: 

        return n 

    return fib(n - 1) + fib(n - 2) 
 
print(fib(10))  # Takes longer!

⚠️ Redundant computations make it slow!

Summary of Characteristics

Characteristic Description
Well-Defined Inputs

Takes valid input values
Well-Defined Outputs

Produces correct outputs
Finiteness

Terminates in a finite number of steps
Definiteness

Clear and unambiguous steps
Effectiveness

Basic operations must be computable
Language Independence

Can be implemented in any programming language
Input Size Independence

Works for any valid input size
Optimality

Uses minimum resources (time & space)

Conclusion

An algorithm is a precise and finite set of instructions to solve a problem. To be valid, it must have definiteness, effectiveness, and finiteness. Optimizing an algorithm makes it more efficient and practical for large-scale problems.

 

Previous
Next