Programming II
Lecture 6:
Algorithm Discovery: Attributes of Algorithms, Measuring Efficiency
Prof. Dr. Slim Abdennadher
[Link]@[Link]
German International University, Faculty of Informatics and Computer Science
Abdennadher (GIU) 1 / 19
Algorithm discovery Attributes of algorithms
Attributes of algorithms
Which characteristics mark a good algorithm?
Correctness
Give a correct solution to the problem!
Ease of understanding
Clarity and ease of handling
Program maintenance
Fix errors
Extend the program to meet new requirements
Efficiency
Time: How long does it take to solve the problem?
Space: How much memory is needed?
Abdennadher (GIU) 2 / 19
Algorithm discovery A choice of algorithms
A choice of algorithms
It is possible to come up with a several different algorithms to solve
one and the same problem
Which one is the best?
Most efficient: Time vs. Space
Easiest to maintain
How do we measure time efficiency?
Running time?
Number of executed operations?
Abdennadher (GIU) 3 / 19
Algorithm discovery Measuring efficiency
Measuring Efficiency
Need a metric to measure efficiency of algorithms
Running Time: How long does it take to solve the problem?
Depends on machine speed
Number of Operations: How many operations does the algorithm
execute?
Better metric but a lot of work to count all operations
Number of Fundamental Operations: How many “fundamental
operations” does the algorithm execute?
Depending on size and type of input, we are interested in:
Best-case, Worst-case, Average-case behavior
Need to analyze the algorithm!
Abdennadher (GIU) 4 / 19
Algorithm discovery Examples: Average
Example: Average of n numbers – counting
Problem: Find the average of n numbers
1 int[] a = {2,4,6,8,10,12};
2 int n = [Link];
3 int sum = 0;
4 int i = 0;
5 while (i < n)
6 {
7 sum += a[i];
8 i++;
9 }
10 int average = sum/n;
11 [Link](average);
How many steps does the algorithm execute?
Steps 1, 2, 3,4, 10, and 11 are executed once.
Steps 5, 7, and 8 depend on the length of the array n.
Abdennadher (GIU) 5 / 19
Algorithm discovery Examples: Average
Example: Average of n numbers – doing the sum
Problem: Find the average of n numbers
1 int[] a = {2,4,6,8,10,12}; 1 operation => executed once
2 int n = [Link]; 1 operation => executed once
3 int sum = 0; 1 operation => executed once
4 int i = 0; 1 operation => executed once
5 while (i < n) 1 operation => (n + 1) repetitions
6 {
7 sum += a[i]; 1 operation => n repetitions
8 i++; 1 operation => n repetitions
9 }
10 int average = sum/n; 1 operation => executed once
11 [Link](average); 1 operation => executed once
Total number of executed operations
1 + 1 + 1 + 1 + (n + 1) + n + n + 1 + 1 = 3n + 7
Abdennadher (GIU) 6 / 19
Algorithm discovery Examples: Sequential search
Sequential search – Analysis
1 String name = "Ahmed";
2 String[] names = {"Aly","Slim", "Ahmed"};
3 int[] IDs = {17,2,8};
4 int n = [Link];
5 int i = 0;
6 boolean found = false;
7 while (found == false && i < n){
8 if ([Link](names[i])){
9 [Link](IDs[i]);
10 found = true;}
11 else
12 i++;}
13 if ( !found )
14 [Link]("sorry, name is not in directory");
How many steps does the algorithm execute?
Abdennadher (GIU) 7 / 19
Algorithm discovery Examples: Sequential search
Sequential search – Analysis
How many steps does the algorithm execute?
Steps 1, 2, 3, 4, 5, 6, 9, 10, 13 and 14 are executed at most once.
Step 7 is executed at most n + 1 times.
Steps 8 and 12 are executed at most n times.
So what is the running time now? (focus on the loop)
Worst case: Steps 8 and 12 are executed at most n times and
step 7 n + 1 times.
Best case: Step 7 is executed exactly twice. Step 8 is executed
only once.
n
Average case: Steps 8 and 12 are executed approximately 2
times.
Abdennadher (GIU) 8 / 19
Algorithm discovery Examples: Sequential search
Sequential search – Worst case behavior
1 String name = "Ahmed"; 1 ops => executed once
2 String[] names={"Aly","Slim","Karim"};1 ops => executed once
3 int[] IDs = {17,2,8}; 1 ops => executed once
4 int n = [Link]; 1 op => executed once
5 int i = 0; boolean found = false; 2 ops => executed once
6 while (found == false && i < n){ 1 op => (n + 1) reps
7 if ([Link](names[i])){ 1 op => n repetitions
8 [Link](IDs[i]); skipped...
9 found = true;} skipped...
10 else i++;} 1 op => (n − 1) reps
11 if (!found) 1 op => executed once
12 [Link]("sorry, name is not in directory");1 op =>
executed once
Assume the name is not in the list!
1 + 1 + 1 + 1 + 2 + (n + 1) + n + (n − 1) + 1 + 1 = 3n + 8
Abdennadher (GIU) 9 / 19
Algorithm discovery Examples: Sequential search
Sequential search – Worst case behavior
1 String name = "Ahmed"; 1 ops => executed once
2 String[] names={"Aly","Slim","Ahmed"};1 ops => executed once
3 int[] IDs = {17,2,8}; 1 ops => executed once
4 int n = [Link]; 1 op => executed once
5 int i = 0; boolean found = false; 2 ops => executed once
6 while (found == false && i < n){ 1 op => (n + 1) reps
7 if ([Link](names[i])){ 1 op => n repetitions
8 [Link](IDs[i]); 1 op => executed once
9 found = true;} 1 op => executed once
10 else i++;} 1 op => (n − 1) reps
11 if (!found) 1 op => executed once
12 [Link]("sorry, name is not in directory");skipped...
Assume the name is the last one in the list!
1 + 1 + 1 + 1 + 2 + (n + 1) + n + 1 + 1 + (n − 1) + 1 = 3n + 9
Abdennadher (GIU) 10 / 19
Algorithm discovery Examples: Print a line of n stars
Example: Print of line of n stars
Problem: Print a line of n stars
1 public static void lineOfStars(int n){
2 int i = 1; 1 ops => executed once
3 String s = ""; 1 ops => executed once
4 while (i <= n){ 1 op => (n + 1) reps
5 s += " * "; 1 op => (n) reps
6 i ++;} 1 op => (n) reps
7 [Link](s);} 1 ops => executed once
How many steps does the algorithm execute?
Steps 2, 3 and 7 are executed once.
Steps 4, 5, and 6 depend on the input n.
Total numbers of executed operations:
1 + 1 + (n + 1) + n + n + 1 = 3n + 4
Order of magnitude: O(n)
Abdennadher (GIU) 11 / 19
Algorithm discovery Examples: Print square of n stars
Example: Print square of n stars
Problem: Print square of n stars using lineofStars
1 int n = 5; 1 ops => executed once
2 int i = 1; 1 ops => executed once
3 while (i <= n){ 1 ops => executed (n+1) reps
4 lineOfStars(n); 1 ops => executed (n*(3n+4) reps
5 i++;} 1 ops => executed once
How many steps does the algorithm execute?
Steps 1 and 2 are executed once.
Steps 3 and 5 depend on the input n.
Step 4 is executed 3n ∗ 4 times each time it is called and depends
on the input n.
Total numbers of executed operations:
1 + 1 + (n + 1) + (n ∗ (3n + 4)) + n = 6n + 3n2 + 3
Order of magnitude: O(n2 )
Abdennadher (GIU) 12 / 19
Algorithm discovery Examples: Print square of n stars
Example: Print square of n stars
Problem: Print square of n stars using nested loops
1 int n =4; 1 ops => executed once
2 for(int i=1; i<=n; i++){1 ops =>executed (1+(n+1)+n)reps
3 for(int j=1;j<=n;j++) 1 ops executed 1+(n+1)*n+(n*n)reps
4 [Link](" * ");1 ops => executed (n*n) reps
5 [Link]();} 1 ops => executed n reps
How many steps does the algorithm execute?
Step 1 is executed once.
Step 2, initialization is executed once, condition & update depend on n.
Step 3, initialization depend on n, condition & update depend on n, n times.
Step 4 is executed n ∗ n times. n times in every iteration of the outer loop
and depends on the input n.
Step 5 depend on n.
Total numbers of executed operations:
1+(1+(n+1)+n)+(n+((n+1)∗n)+(n∗n))+(n∗n)+n = 5n+3n2 +3
Abdennadher (GIU) 13 / 19
Order of magnitude What really matters
What really matters
We are
not interested in knowing the exact number of operations the
algorithm performs.
mainly interested in knowing how the number of operations grows
with increased input size!
Why?
Given large enough input, the algorithm with faster growth will
execute more operations.
Consider algorithms A and B with input size n = 10, 000:
Algorithm A has a running time of 570n + 920 operations
→ 5,700,920 operations.
Algorithm B has a running time of n2 + 21 operations
→ 100,000,021 operations.
Algorithm B takes already twenty times longer!
Abdennadher (GIU) 14 / 19
Order of magnitude Big-O notation
The “Order of Magnitude”
The Order of Magnitude is a formula that strips away all ballast. For
example. . .
n
6n
6n + 278
5000n + 2000
Are all in the Order of Magnitude of n
n3
200n3 + 150n + 20
50n3 + n2
Are all in the Order of Magnitude of n3
Abdennadher (GIU) 15 / 19
Order of magnitude Big-O notation
The “Big O notation”
We write O(n) for the Order of Magnitude of n.
Generally, if a function g is in the Order of Magnitude of a function
f , we write (g = O(f )).
For your reference. . .
Formally, the Order of Magnitude is defined as:
∃c. ∃n0 . ∀n > n0 . c · f (n) >= g(n) ⇔ g = O(f )
You are only interested into the fastest growing part of the function you
have!
Abdennadher (GIU) 16 / 19
Order of magnitude Big-O notation
Beware of fast growth!
Imagine algorithms A, B, and C, with
A in O(n),
B in O(n2 ), and
C in O(2n )
1
Consider an operation taking 100 s
n 10 20 30 40
1 2 3 4
A 10 s 10 s 10 s 10 s
B 1s 4s 9s 16s
C ca. 10s ca. 3h ca. 4 months ca. 348 years
Abdennadher (GIU) 17 / 19
Order of magnitude Big-O notation
Some terms
Algorithms in O(1) are called constant
Algorithms in O(n) are called linear
Generally, algorithms in O(nx ) for some x are called polynomial
(constant, linear, quadratic, cubic, . . . )
Algorithms in O(2n ) are called exponential
Abdennadher (GIU) 18 / 19
Summary
Summary
We are concerned about the efficiency of algorithms
Time and space efficiency
An analysis of the algorithm is necessary
The order of magnitude (Big O notation) measures efficiency
O(1), O(n), O(n2 ), . . .
Measures the growth with increasing input size n
Aim for low growth rates
Abdennadher (GIU) 19 / 19