Test: Algorithm Analysis & Asymptotic Notation- 2 - Computer Science Engineering (CSE) MCQ

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

The notation O(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worstcase time complexity of the algorithms.

Let's analyze the functions and their growth rates to determine which of the statements is true.

In this programme for loop run n/2 times and in this ‘for loop’ y(i) have (log₂ n) time complexity. In the above we will select maximum time complexity i.e., (n/2) log₂n.
Then the total time complexity for the ‘for loop’ will O(n logn).

The given C function is recursive. The best way to find the time complexity of recursive function is that convert the code (algorithm) into recursion equation and solution of the recursion equation is the time complexity of given algorithm.

1. int recursive (int i){
2 . if ( n == 1) return (1);
3. else
4. return (recursive(n-1) + recursive(n-1));
5. }
Let recursive(n) - T(n)
According to line 2 if (n = = 1) return(1) then the recursive equation is
T(n) = 1, n = 1
According to line 4 the recursion equation is
T(n) = T ( n - 1 ) + T(n-1), n > 1
So the complete recursion equation is 

By substitution method

T(0)= T(1) = 1 
T(n) = 2T(n/2) + n
T(n) be computed as follows:

[T(n) can also proved by Master Theorem]
if  then it is also 0(n logn) and O(n²) but it is not Ω(n²).

Let the increment of j is 2°, 2¹...., 2ⁱ for some value of i so according to the question for while loop: 

One extra comparison required for the termination of while loop. So total number of comparisons 

The given function is recursive so the equivalent recursion equation is

All the level sums are equal to n. The problem size at level k of the recursion tree is n^2-k and we stop recursing when this value is a constant. Setting n^2-k = 2 and solving for k gives us  

It takes not more than n/2 comparison to check whether the given number n is prime or not.

Since q is constant, so our recurrence relation look like

Two cases: Q(m, 3)
(i) m ≥ n : here m ≥ 3 
For

∵ Since 3 is divide by 3 only 1 time = 0 + P= P.
So this recursive program generate P, m/n times until m < n.
So, Q(m, 3) = Px(m div 3)

By using recursive tree method:

So, height of tree is log_(3/2)n
So, T(n) = Height x Work at each level.

So, order of algorithm
 

T(n) = mT (n/2) + an²
Since,
m ≥ 5 
So by applying Master Theorem: