Q1- An algorithm is made up of 2 modules m1 and m2. If order of m1 is f(n) an m2 is g(n) then the order of the algorithm is
(a) f(n) + g(n)
(b) min(f(n), g(n))
(c) max(f(n), g(n))
(d) f(n)*g(n)
(c)
int main()
{
for(i=1;i<=n;i++)
{
//This for loop has no of operations n.
}
for(j=1;j<=n;j=j*2)
{
//This for loop has no of operations logn.
}
}
The time complexity is max(n, logn) = O(n)
Q2- The concept of order big-oh is important because
(a) It is the lower bound of the growth rate of the algorithm.
(b) It can be used to decide the best algorithm that solves a given problem.
(c) It determines the maximum size of a problem that can be solved in a given system, in a given amount of time.
(d) none of the above.
(b) and (c)
Big-Oh will give the worst case of the algorithm so it determines the best algorithm which will not bigger amount of time.
Q3- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)=T(n-1) + a, if n>1
     b    , if n≤1Â
Where a, b, c are constants. The time complexity of the algorithm is
(a) n2
(b) n3
(c) nn
(d) n
(d)
T(n) = T(n-1) + c
T(n-1) = T(n-2) + c
T(n-2) = T(n-3) + c
…
T(2) = T(1) + c
T(1) = b
———————
T(n) = (n-1)c + b
T(n) = O(n)
Q4- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)= 8T(n/2) + an, if n>1
      b      , if n=1
Where a, b are constants. The time complexity of the algorithm is
(a) n2
(b) n3
(c) nn
(d) n
(b)
Apply master’s theorem
Compiling time – n^log28 = n3
Running time – n
The answer is n3.
Q5- There are four different algorithms A1, A2, A3, A4 to solve a given problem with the order of log(n), log(logn), nlog(n) and n/log(n) respectively. Which is the best algorithm?
(a) A1
(b) A2
(c) A3
(d) A4
(b)
Suppose n = 2^2^2
A1 = log(n) = log(2^2^2) = 2^2 = 4
A2 = log(logn) = log(log(2^2^2)) = 2
A3 = nlog(n) = 2^2^2log(2^2^2) = 16*4 = 64
A4 = n/log(n) = 2^2^2/log(2^2^2) = 64/4 = 16
Answer is A2