Introduction to Algorithm Analysis and the RAM Model

Multiplicity of Solutions for Computational Problems

  • A single computational problem often has multiple possible solutions or algorithms.

  • An example of this is the Sorting Problem, which can be addressed using several different algorithms:

    • Bubble Sort

    • Selection Sort

    • Insertion Sort

    • Merge Sort

    • Quick Sort

    • Heap Sort

  • Determining which algorithm to choose depends on specific criteria:

    • Ease of understanding and coding.

    • Resource usage, specifically Processor time and Memory Space.

Theoretical Basis of Algorithm Analysis

  • Analyzing algorithms involves predicting the resources they require.

  • Primary resources considered are:

    • Computational time.

    • Memory for storage.

  • The goal of analysis is to identify the most efficient algorithm for a specific problem in terms of time and space complexity.

  • Approaches to calculating running time:

    • Empirical Analysis: This involves writing the program and measuring actual execution time. However, this method is dependent on specific implementations, including the programming language used, the machine hardware, and the compiler. It also depends on the nature of input test cases.

    • Apriori Analysis: This involves calculating running time before any coding occurs. It is an implementation-independent, theoretical approach based on a machine model.

The Random Access Machine (RAM) Model of Computation

  • A benchmark or model is required to understand implementation technology and the costs of resources.

  • The analysis assumes a generic, one-processor Random Access Machine (RAM) model of computation.

  • Key characteristics of the RAM model include:

    • Algorithms are implemented as computer programs.

    • Instructions are executed sequentially, one after another.

    • No concurrent operations are permitted.

    • Every arithmetic operation, data movement, and transfer of control takes a constant amount of time.

  • The RAM contains instructions common to real computers:

    • Arithmetic: addadd, subtractsubtract, multiplymultiply, dividedivide, remainderremainder, floorfloor, and ceilceil.

    • Data movement: loadload, storestore, and copycopy.

    • Control: Conditional and unconditional branch, subroutine call, and return.

Defining Running Time and Primitive Operations

  • Each statement in an algorithm is translated into a set of primitive operations or steps.

  • The running time of a statement depends on the number of primitive operations it contains.

  • For example, the statement z=x+yz = x + y can be translated for a hypothetical machine as follows:

    1. load r1,xload\,r1, x (loads contents of memory location xx to register r1r1).

    2. load r2,yload\,r2, y (loads contents of memory location yy to register r2r2).

    3. add r1,r2add\,r1, r2 (adds contents of r1r1 and r2r2, storing the result in r1r1).

    4. store z,r1store\,z, r1 (moves data in r1r1 to memory location zz).

  • In this scenario, the operation z=x+yz = x + y requires 4 machine instructions.

  • The number of steps varies for different types of statements.

  • Formally, the running time of an algorithm on a particular input is the number of primitive operations or steps executed.

  • Each line in the pseudocode takes a constant amount of time. The ithi^{th} line takes time cic_i, where cic_i is a constant.

Example: Simple Arithmetic Procedure

  • Procedure: sample(a,b)sample(a, b)

    1. c=a−bc = a - b

    2. temp=atemp = a

    3. a=ba = b

    4. b=tempb = temp

    5. return creturn\,c

  • Cost Breakdown:

    • Line 1: Cost c1c_1, performed 1 time.

    • Line 2: Cost c2c_2, performed 1 time.

    • Line 3: Cost c3c_3, performed 1 time.

    • Line 4: Cost c4c_4, performed 1 time.

    • Line 5: Cost c5c_5, performed 1 time.

  • Total Running Time: T=c1+c2+c3+c4+c5T = c_1 + c_2 + c_3 + c_4 + c_5

Example: Array Summation Algorithm

  • Procedure: Array−Sum(A)Array-Sum(A)

    1. sum=0sum = 0

    2. for i=1 to A.lengthfor\,i = 1\,to\,A.length

    3. sum=sum+A[i]sum = sum + A[i]

    4. return sumreturn\,sum

  • Cost and Execution Frequency (where nn represents A.lengthA.length):

    • Line 1: Cost c1c_1, occurs 1 time.

    • Line 2: Cost c2c_2, occurs n+1n + 1 times (the extra time is for the final check that terminates the loop).

    • Line 3: Cost c3c_3, occurs nn times.

    • Line 4: Cost c4c_4, occurs 1 time.

  • Running Time Calculation:

    • T(n)=c1(1)+c2(n+1)+c3(n)+c4(1)T(n) = c_1(1) + c_2(n + 1) + c_3(n) + c_4(1)

    • After distributing and grouping terms:

    • T(n)=(c2+c3)n+(c1+c2+c4)T(n) = (c_2 + c_3)n + (c_1 + c_2 + c_4)

    • This results in a linear function: T(n)=an+bT(n) = an + b

Analysis of Search and Count Algorithms

  • Linear-Search(A, key)

    1. for i=1 to A.lengthfor\,i = 1\,to\,A.length

    2. if A[i]==keyif\,A[i] == key

    3. return ireturn\,i

    4. return −1return\,-1

  • Count-Occurrence(A, key)

    1. count=0count = 0

    2. for i=1 to A.lengthfor\,i = 1\,to\,A.length

    3. if A[i]==keyif\,A[i] == key

    4. count=count+1count = count + 1

    5. return countreturn\,count

  • Running Time for Count-Occurrence:

    • Line 1: c1c_1

    • Line 2: c2(n+1)c_2(n + 1)

    • Line 3: c3nc_3n

    • Line 4: c4nc_4n

    • Line 5: c5c_5

    • Total T(n)=c1+c2(n+1)+c3n+c4n+c5T(n) = c_1 + c_2(n + 1) + c_3n + c_4n + c_5

    • This also fits the linear function model T(n)=an+bT(n) = an + b, where nn is the input size.

  • Search-Multiple(A, B)

    1. count=0count = 0

    2. for i=1 to B.lengthfor\,i = 1\,to\,B.length

    3. key=B[i]key = B[i]

    4. for j=1 to A.lengthfor\,j = 1\,to\,A.length

    5. if A[j]==keyif\,A[j] == key

    6. count=count+1count = count + 1

    7. return countreturn\,count