CS 502 Summer 2006
Analysis Of Algorithms University of Bridgeport
Analysis of Algorithms
The field of computer science that studies efficiency of algorithms is known as analysis of algorithms.
Example 1:
Bubblesort requires n^{2} statements to sort n elements for a given time interval
If computing speed is increased by 1,000,000, then 1,000,000n^{2} statements can be executed in the same time interval.
But, 1,000,000n^{2} = (1000n)^{2}
i.e. 1000n elements can be sorted which is an ^{ }increase (we lost 3 of 6 orders of magnitude)
Example 2:
Swap down in heapsort requires lg(n) statements for n elements for a given time interval
If computing speed increased by 16, then 16lg(n) statements can be executed in the same time interval.
But, 16lgn = lg(n^{16}) [since ]
i.e. n^{16 }elements can be processed, which is an exponential increase
Algorithms for which problem size, which can be solved in the same time interval increase linearly with computing speed are called linear complexity algorithms.
This information has been summarized in the table below:
Table 1: Effect of algorithm efficiency on ability to benefit from increases in speed
Algorithm Complexity

Linear i.e. n

Quadratic i.e. n2

Logarithmic i.e. lg(n)

Increase in computing speed

1,000,000 (10^{6})

1,000,000 (10^{6})

1,000,000 (10^{6})

Equivalent problem size that can be solved in the same amount of time

1,000,000n (10^{6})

1000n (10^{3})

(to the power of 10^{6})

Benefit from increases in speed

Linear


Exponential

Complexity of Algorithm Depends On Algorithm Implementation:
Example 1: Bubblesort
Code: for i:= 1 to n1 line 1
for j:= 1 to n1 line 2
