Algorithm Efficiency In computer science BigO notation descr

Algorithm Efficiency: In computer science, Big-O notation describes efficiency of an algorithm. An inefficient algorithm is slow, whereas an efficient algorithm is fast Speed also depends on the amount of data involved, which is N. Big-0 notations for algorithms include Logarithmic: log_2(N) Linear. N Exponential: 2^N Line arithmetic: Nlog_2(N) Quadratic: N^2 Cubic: N^3 Calculate the rates of change (speeds) for each of the above notations when N=10 and when N=100. When N=10, which type of algorithm is the fastest? Which is the slowest? When N=100, which type of algorithm is the fastest? Which is the slowest? The bigger N is, do the algorithms run slower or faster?

Solution

1. The rates of change for each are

O(log2 N) : log2(10) = 3.322, log2(100) = 6.644 : rate of change = (6.644 - 3.322) / (100 - 10) = 0.0369

O(N) : (100 - 10) / (100 - 10) = 1

O(2^N) : (2^100 - 2^10) / (100 - 10) = 1.4085 x 10^28 (Very Large)

O(N log2 N) : (100*6.644 - 10*3.322) / (100 - 10) = 7.013

O(N^2) : (100^2 - 10^2) / (100 - 10) = 110

O(N^3) : (100^3 - 10^3) / (100 - 10) = 11100

2. When N = 10, Logarithmic O(log2 N) is the fastest as it takes 3.322 steps to complete. 2^10 = 1024 which is the largest among all (Note: 10^3 is close at 1000 ). Therefore, Exponential O(2^N) is the slowest.

3. When N = 100, Logarithmic O(log2 N) is the fastest and Exponential O(2^N) is the slowest.

4. The bigger N is, an algorithm will run slower as it would have to compute for more input data.