Design and Analysis of Algorithms

• Design and Analysis of Algorithms is taught by Prof. Sufiya Ahmed at R.D. National College for SYCS students

Algorithm Origins and Definition

• The term "Algorithm" originates from the Persian author Abu Jafar Mohammad Musa Al-Khowarizmi
• An algorithm is a solution, procedure, or method used in computer science to solve a problem
• Algorithms are a finite number of steps to solve a task in a finite number of times

Algorithm in Practice

• An algorithm is a step-by-step process for performing an action
• It transforms an input list into an output list through a series of steps

Common Algorithm Terms

• Variables: Specific locations in computer memory that store one value
  • Examples: a, x, i
• Data Type: Categorizes the type of values a variable can hold
  • Examples: Float, Integers, Strings, Booleans
• Statement: A line of code

Algorithm Properties

• Input: Algorithms take input, processing it to produce output
• Output: Algorithms produce specific outputs for each input
  • Example: A program checks if a number is prime and outputs "No. is prime" or "No. is not prime"
• Precision (Precisely Defined): Measures how consistently the algorithm produces reliable results
• Correctness: Algorithms produce the correct output for all valid inputs
• Finiteness: Algorithms produce output after a finite number of steps for each input
• Determinism: Algorithms guarantee a result
• Generality: Procedures apply to all problems, not just a special subset

Algorithm Design

• Algorithms can be designed using natural language, pseudo code, or flowcharts
• Natural language is understandable to humans but not machines
• Pseudo code is understandable to both humans and machines, bridging natural language and complex programming
• Flowcharts provide a visual representation of the algorithm's steps

Algorithm Analysis Types

• Used when algorithms are analyzed to understand their efficiency
• Done in two ways: Priori analysis and Posteriori analysis

Priori Analysis

• Analysis done before implementation to test the algorithm
• Examines the logic of the algorithm and determine the number of steps, or the memory space used by it when executed with an input of a particular size
• Mathematics are used to predict how well the algorithm will perform
• A sorting algorithm with n elements taking O(n log n) steps serves as an example
• Factors like computer type or programming language are not considered

Posteriori Analysis

• Analysis done after the implementation to test the algorithm
• Measures how much time the algorithm takes and how much memory it uses
• Performance depends on real-world environment
  • Computer Speed
  • Programming Language Efficiency
  • Input Data Types
• Running a sorting algorithm on a dataset to find it used 10 MB of memory and took 5 seconds is an example

Asymptotic Notations

• Big O Notation: Represents the upper bound, or maximum time, of an algorithm's runtime
• Omega (Ω) Notation: Represents the lower bound, or minimum time, of an algorithm's runtime
• Theta (Θ) Notation: Represents the average time of an algorithm's runtime

Time Complexity - Big O

• The time complexity refers to the amount of time it takes for an algorithm to run as a function of the input size

Example 1 - Swap two numbers

• A function to swap two numbers will not be considered, and takes one unit of time

def swap_using_temp(a, b): 
    temp = a  # 1 unit of time
    a = b  # 1 unit of time
    b = temp  # 1 unit of time

• The total time is 3 units of time
• The Time Complexity is f(n) = O(3) which becomes O(1)

Example 2 (A):

for i in range(n): #not consider condition
    # some operation #It will execute n number of times = n unit of time
    print(i) #Constant time operation

• It will execute n number of times which is n unit of time
• The Time Complexity is f(n) = O(n)

Example 2 (B):

for (i=1; i<=n; i++) #not consider condition
{
    Statement; # It will execute n number of times = n unit of time
}

• It will execute n number of times which is n unit of time
• The Time Complexity is f(n) = O(n)

Example 3:

for (i=1; i<=n; i++) #not consider condition
{
    Statement a # n units of time
}
for (j=1; j<=n; j++) #not consider condition
{
    Statement b # n units of time
}

• By using Third Rule, coefficients are not considered
• Total: f(n) = O(2n) = O(n）

Third Rule

• Coefficients are not considered
• After some time the power term > coefficient term
• Therefore, coefficients are ignored

Example 4 (A):

for i in range(n): # Outer loop: runs n times
    for j in range(m): # Inner loop: runs m times
        print(i, j)  # Constant time operation

• Time Complexity: O(n x m)
• If m = n, the complexity becomes: O(n²)

Example 4 (B):

for (i=1; i<=n; i++) #not consider condition
    {
        for (j=1; j<=n; j++) #not consider condition
            {
                statement #n units of time
            }
    }
O(n x n)
Time Complexity: O(n²)

i    j
1    n no. of times
2    n no. of times
3    n no. of times
.    .
.    .
.    .
n    n no. of times

n x n = n2

Time Complexity: f(n) = O(n²)

Example 5:

def check_even_odd(number): #will not consider a function
    if number % 2 == 0:  # not consider condition
        print(f" {number} is even.") #1 unit of time
    else: # not consider condition
        print(f" {number} is odd.") #1 unit of time        

Total: 2 Unit of time Time Complexity: f(n) = O(1) Note: If term is constant or non changing factor, {Replace with 1}

Space Complexity

• Determining the efficiency of an algorithm is an important parameter
• A program's memory is used for variables, program instructions, and execution
  • Note: For space complexity, the variables are checked
• An algorithm's amount of memory space, including the input values for execution, is considered
• Space Complexity = Auxiliary Space + Space used by input values
• User → A[] → Input Values → Space used by input values are needed
• A place to store values in array we use for loop → i variables → auxiliary space

Space Complexity examples

• Compiler → Integer → 2 and 4 bytes Example 1:

int sum (int x, int y, int z)
    {
        int t = x + y + z;
        return t;
    }

x --> 2 bytes
y --> 2 bytes
z --> 2 bytes
t --> 2 bytes
return --> 2 bytes
Total: 10

Space Complexity = O(10) = O(1)

Example 2:

int sum (int a[], int n)
{
    int r = 0;
    for (int i = 0; i<n; i++)
        {
            r += a[i];
        }
    return r;
}

h --> 2
a[] --> 2n
r --> 2
i --> 2
return --> 2

By First Rule: The higher factor of 2n is considered By Third Rule: power values are considered and coefficients (2 discarded) Space Complexity = O(n)

Example 3:

int a = 0, b = 0;
for (i=0; i<n; i++)
{
    for (j = 0; j<n; j++)
    {
            a = a+j;
    }
}
for (k=0; k<n; k++)
{
   b = b+k;
}

a-->2
b-->2
i-->2
n-->2
j-->2
k-->2
12

Space Complexity = O(1)

Example 4:

matriAdd (int a[], int b[], int c[], int n)
{
    for (int i = 0; i<n; i++)
    {
        c[i] = a[i] + b[i];
    }
}
 a[] --> 2n
 b[] --> 2n
 c[] --> 2n
 n --> 2
 i --> 2
     
6n + 4

Space Complexity = O(n)

Algorithm Comparison

Best way to compare algorithms

• Compare the running time of algorithms. by expressing it as a function of input size n = f(n).

Other ways to compare algorithms (not best way).

• Other metrics, like execution time and number of statements, depend on system, programming language, and programmer.

Rate of Growth

• The rate at which running time increases is a function of input
• Example:
  • Price of x = 40000
  • Price of y = 50 (small values neglected). and the total cost is equal to the most expensive value
  • and the highest value is the rate of growth
  • F = n5, n4, n² : n5 is the rate of growth

Types of Analysis

• Worst Case
  • Input for which the algorithm takes the maximum time to find solution.
  • For this input there is slowest execution of algorithm.
• Best Case:
  • Input for which the algorithm takes minimum time to find solution.
  • For this input algorithm executes fastest.
  • Best Case Time ≤ Average Case Time ≤ Worst Case Time
• Average Case:
  • Algorithm with prediction on running time is used
  • Input is random and algorithm is executed many times.
  • Average for all input is taken.