GHANA COMMUNICATION TECHNOLOGY UNIVERSITY
FACULTY OF COMPUTING AND INFORMATION SYSTEM
DEPARTMENT OF COMPUTER SCIENCE
COURSE: ANALYSIS AND DESIGN OF ALGORITHMS
COURSE CODE: CSSD 301
LECTURER: MR. PAUL AAZAGREYIR
ASSIGNMENT
NAME: PRINCE OFOSU FIEBOR
INDEX NUMBER: 4231230054
SESSION: MORNING (GROUP C)
The worst case analysis is the most important because, it helps the programmer know the maximum resources to
1.
be used. And by knowing, it helps them develop and provide efficient and reliable systems which improves the
performance of systems.
Exponential complexities must be avoided at all cost because it leads to extremely high and unmanageable
2.
computational demands and input date gross. And can also lead to unacceptable delays or crashes.
Analysis of an algorithm provides us with the efficiency of an algorithm in terms of space and time.
3.
4.
Computer A= 1 minute
Problem size
Problem instance = 1000
Computer B= 1000 times of computer A
Solution
* Linear complexity = O (n)
Computer A solves problem size
n=1000 in one minutes.
Computer B solve problem size
n = 1000 * computer A in one minute.
⸫ Computer B= 1000*1000
(n) = 1000*1000
=1,000,000.
⸫Computer b can run instance size n= 1,000,000 in 1 minute.
* Logarithmic Complexity = O(log(n))
Computer A solves problem size n in 1 minute = O(log(1000))
=3
Computer B is 1000 times faster than Computer A = 1000 * O(log(1000))
=3000.
⸫ Computer B can run instances size n = 3000 in 1 minute.
* Linearithmic Complexity = O(n log n)
Computer A solves problem size n in 1 minute = O(1000 * log 1000)
=3000
Computer B is 1000 times faster than computer A = 1000 * O(100 * log 1000)
=3000000.
⸫ Computer B can run instances size n = 3000000.
* Quadratic Complexity = O(n2)
Computer A solves problem size n in 1 minute = O(1000 * 1000)
= 1000000
Computer B is 1000 times faster than Computer A = 1000 * O(log(1000))
=1000000000
⸫ Computer B can run instances size n = 1000000000 in 1 minute.
* Cubic Complexity = O(n3)
Computer A solves problem size n in 1 minute = O(1000 * 1000 * 1000)
= 1000000000
Computer B is 1000 times faster than Computer A = 1000 * O(1000 * 1000 *1000)
=1000000000000.
⸫ Computer B can run instances size n = 1000000000000 in 1 minute.
