Lecture 3: Algorithms Analysis
Algorithm Complexity
Examples of Operations
Purely computational Operations :
1) Basic operations
• Arithmetic operations
• Comparison operations
• Assignment operations
2) Non-basic operations
• Searching within a database that fits in RAM for a given value
• Running a regular expression pattern match on a string
Code to retrieve the maximum element in an array
int max = arr[0];
for (int i = 1; i < n; i++ ) {
if ( arr[i] >= max ) {
max = arr[i];
}
}
Assuming processor can execute the following operations as one instruction each:
—Assigning a value to a variable
—Looking up the value of a particular element in an array
—Comparing two values
—Incrementing a value
—Basic arithmetic operations such as addition and multiplication
1) No of instructions = 2 →Look-up and Assignment
The algorithm always requires these two instructions, regardless of the value of n.
, 2) The for loop initialization code has to always run
No of instructions = 2 →Assignment and Comparison
These will run before the first for-loop iteration.
3) After each for-loop iteration, we need 2 more instructions to run
No of instructions = 2 →Increment
➔ Comparison
4) Looking at the for body, we have 2 instructions that happen always
→ Lookup and Comparison
If it happens to be so that arr[ i ] >= max, then we'll run these 2 additional
instructions →Lookup and Assignment.
If we ignore the loop body, the number of instructions this algorithm needs is 4 +
2n.
int max = arr[0];
for (int i = 1; i < n; i++ ) {
}
➔ 4 instructions at the start
➔ 2instructions for each of the n iterations
Mathematical function f(n) gives us the number of instructions the algorithm needs
➔ f(n) = 4 + 2n
We can't define an f(n) as easily, because our number of instructions doesn't depend
solely on n but also on our input.
Algorithm Complexity
Examples of Operations
Purely computational Operations :
1) Basic operations
• Arithmetic operations
• Comparison operations
• Assignment operations
2) Non-basic operations
• Searching within a database that fits in RAM for a given value
• Running a regular expression pattern match on a string
Code to retrieve the maximum element in an array
int max = arr[0];
for (int i = 1; i < n; i++ ) {
if ( arr[i] >= max ) {
max = arr[i];
}
}
Assuming processor can execute the following operations as one instruction each:
—Assigning a value to a variable
—Looking up the value of a particular element in an array
—Comparing two values
—Incrementing a value
—Basic arithmetic operations such as addition and multiplication
1) No of instructions = 2 →Look-up and Assignment
The algorithm always requires these two instructions, regardless of the value of n.
, 2) The for loop initialization code has to always run
No of instructions = 2 →Assignment and Comparison
These will run before the first for-loop iteration.
3) After each for-loop iteration, we need 2 more instructions to run
No of instructions = 2 →Increment
➔ Comparison
4) Looking at the for body, we have 2 instructions that happen always
→ Lookup and Comparison
If it happens to be so that arr[ i ] >= max, then we'll run these 2 additional
instructions →Lookup and Assignment.
If we ignore the loop body, the number of instructions this algorithm needs is 4 +
2n.
int max = arr[0];
for (int i = 1; i < n; i++ ) {
}
➔ 4 instructions at the start
➔ 2instructions for each of the n iterations
Mathematical function f(n) gives us the number of instructions the algorithm needs
➔ f(n) = 4 + 2n
We can't define an f(n) as easily, because our number of instructions doesn't depend
solely on n but also on our input.
