Best, Worst and Average case
Best case complexity gives lower bound on the running time of the algorithm for any instance of input(s). This indicates that the algorithm can never have a lower running time than best case for particular class of problems.
Worst-case complexity gives the upper bound on the running time of the algorithm for all the instances of the input(s). This ensures that no input can overcome the running time limit posed by worst-case complexity.
Average case complexity gives the average number of steps required on any instance of the input(s).
In our study, we concentrate on worst-case complexity only.
Example 1: Fibonacci Numbers
Input: n
Output: nth Fibonacci number.
Algorithm: assume a as first(previous) and b as second(current) numbers
fib(n)
{
a = 0, b= 1, f=1 ;
for(i = 2 ; i <=n ; i++)
{
f = a+b ; a=b ; b=f ;
}
return f ;
}
Efficiency
Time Complexity: The algorithm above iterates up to n-2 times, so time complexity is O(n).
Space Complexity: The space complexity is constant i.e. O(1)
Mathematical Foundation
Since mathematics can provide a clear view of an algorithm. Understanding the concepts of mathematics is an aid in the design and analysis of good algorithms. Here we present some of the mathematical concepts that are helpful in our study.
Exponents
Some of the formulas that are helpful are:
X^a x^b = x^(a+b)
X^a / x^b = x^(a-b)
(x^a)^b = x^ab
X^n + x^n = 2(x^n)
2^n + 2^n = 2^(n+1)
Logarithms
Some of the formulas that are helpful are:
1. logab = logcb / logc a ; c>0
2. log ab = log a + log b
3. log a/b = log a - log b
4. log (a^b) = b log a
5. Log x < x for all x>0
6. Log 1 = 0, log 2 = 1, log 1024 = 10.
7. alogb^n = nlogb^a
Post A Comment:
0 comments so far,add yours