Scribd
Upload
19 views

Analys and Design of Algorithm

Uploaded by

princefiebor10
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
19 views

Analys and Design of Algorithm

Uploaded by

princefiebor10
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

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.

You might also like