16. What do you mean by ²Best case-Efficiency” of an algorithm?
The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.
17. Define the ²Average-case efficiency” of an algorithm?
The ²Average-case efficiency” of an algorithm is its efficiency for the input of size n, for which the algorithm runs between the best case and the worst case among all possible inputs of that size.
18. What do you mean by “Amortized efficiency”?
The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.
19. How to measure the algorithm’s efficiency?
It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.
Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.
20. What is called the basic operation of an algorithm?
The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.
21. How to measure an algorithm’s running time?
Let Cop be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm. Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula
T(n) ≈ Cop C(n)
22. Define order of growth.
The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth we use three notations
1) O (Big oh) notation
2) Ω (Big Omega) notation &
3) Θ (Big Theta) notation
23. Define Big oh notation May/June 2006, April/May 2008
A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n > n0
24. Prove that 100n+5 Î O (n2)?
Clearly 100n+5 £ 100n+n (for all n ³ 5) = 101n£101n2
By choosing n0=5 and c=101 we find that 100n+5ÎO (n2).
25. Define Ω notation
A function t(n) is said to be in Ω (g(n)), denoted t(n) Î Ω (g(n)), if t(n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n0 such that
T (n) < c g (n) for n > n0
26. Prove that n3ÎW(n2)?
Clearly n3 ³ n2 for all n ³ 0. i.e., we can select c=1 and n0=0.
27. Define Θ - notation
A function t(n) is said to be in Θ(g(n)), denoted t(n) Î Θ (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some non negative integer n0 such that
c2 g (n) < t (n) < c1 g(n) for n > n0
28. Prove that( ½)n(n-1) Î Q(n2)
1/2n(n-1)=(1/2)n2-1/2n £ 1/2 n2 for all n³0.(we have proved upper inequality) now 1/2n(n-1)=(1/2)n2-1/2n³(1/2)n2-1/2n*1/2n(for all n³2)=1/4 n2 hence we can select c2=1/4,c1=1/2 and n0=2.
29. What is the use of Asymptotic Notations?
The notations O, W and Q and are used to indicate and compare the asymptotic orders of growth of functions expressing algorithm efficiencies.
No comments:
Post a Comment