Efficiency of Algorithms
Tuesday, 06 February 2024 21:09
Chapter's Topics:
1. Definition
2. Common Algorithms
3. Big-O Notation
Topic 1: Definition Important Definitions:
• Measure the efficiency of an algorithm to determine if it is efficient
• Type of construct used in the algorithm determines efficiency Types of constructs:
• decision
• repetition
• sequence
Topic 2: Common Algorithms
Logarithmic algorithm
number the controls the loop
number of times the loop is repeated
#include <iostream>
using namespace std;
int main(){
int i = 1, n;
cout << "Enter a value for n: ";
cin >> n;
while(i <= n){
i *= 2;
cout << i << " ";
}
return 0;
}
Linear algorithm
number that controls the loop
number of times the loop is repeated
#include <iostream>
using namespace std;
int main(){
int n;
cout << "Enter a value for n: ";
cin >> n;
cout << "\nLooping " << n << " times.\n" << endl;
for(int i = 1; i <= n; i++){
cout << "Value of n = " << n << endl;
cout << "Value of i = " << i << endl;
cout << endl;
}
return 0;
}
Linear logarithmic algorithm
number that controls the loop
number of times the loop is repeated
#include <iostream>
COS1521 - Computer Systems Page 1
number of times the loop is repeated
#include <iostream>
using namespace std;
int main(){
int n;
cout << "Enter a value for n: ";
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
cout << endl;
cout << "n = " << n << endl;
cout << "i = " << i << endl;
cout << "j = " << j << endl;
}
}
return 0;
}
Quadratic algorithm
number that controls the loop
number of times the loop is repeated
#include <iostream>
using namespace std;
int main(){
int a, b;
cout << "Enter a value for a and b: ";
cin >> a >> b;
for(int i = 1; i <= a; i++){
for (int j = 1; j < b; j++){
cout << "Value of a = " << a << endl;
cout << "Value of b = " << b << endl;
cout << "Value of i = " << i << endl;
cout << "Value of j = " << j << endl;
cout << endl;
}
}
return 0;
}
Exponential
#include <iostream>
using namespace std;
long fibonacci(long temp);
int main(){
int input;
cout << "Enter a number to do the Fibonacci sequence on: ";
cin >> input;
cout << fibonacci(input);
return 0;
}
long fibonacci(long temp){
if(temp == 0 || temp == 1){
return temp;
}
return (fibonacci(temp - 1) + fibonacci(temp - 2));
}
COS1521 - Computer Systems Page 2
Topic 3: Big-O Notation
Efficiency Big-O
Logarithmic
Linear
Linear Logarithmic
Quadratic
Polynomial
COS1521 - Computer Systems Page 3
