NPTEL MOCK

Question

Comments

theta of n is correct

Answer 1

Answer provided is wrong

$$T(n) = 2T(\frac{n}{2})+1$$

when decomposed repeatedly you will get $$T(k) =2^k T(\frac{n}{2^k})+k$$

We know that $\because T(1) =2$

substitute $\dfrac{n}{2^k}=1 \implies n= 2^k \implies \log_2n = k$

$\because$ We are doing asymptotic/polynomial analysis we just consider log, and ignore the bases

$$\boxed{n\times T(1)+\log(n)}$$

 

Take the highest order term:

$$\boxed{\Theta(n)}$$

---

3rd Option is accurate.

Answer 2

Step 1: Apply the Master Theorem

 

The recurrence relation is $T(n) = 2T(\frac{n}{2}) + 1$.

This fits the Master Theorem format $T(n) = aT(\frac{n}{b}) + f(n)$ with $a=2$, $b=2$, and $f(n)=1$.

We compare $f(n)$ with $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. Here, $f(n) = 1$, which is $O(n^{1-\epsilon})$ for any $\epsilon > 0$.

This corresponds to Case 1 of the Master Theorem.

 

Step 2: Determine the asymptotic complexity

According to Case 1 of the Master Theorem, if $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$.

In this case, $T(n) = \Theta(n^1) = \Theta(n)$.

 

Answer:  The correct option is $\mathbf{\Theta(n)}$.

 

Answer 3

.