GO Classes CS Test Series | Algorithms | Topic Wise Test 2 | Question: 4

Answer 1

First, notice that $8^{\lg n}=n^{\lg 8}$ (this can be seen by taking $\lg$ of both sides). Since $\log _{4} 64=\lg 8=3$, we use case (ii) of the Master Theorem: $T_{2}(n)=\Theta\left(n^{3} \log n\right).$

Comments

N^3 is understandable how logn came sir,

---

@princeit07 Refer this

$T(n) = 64T(\frac{n}{4}) + 8^{log_2n}$

= $64T(\frac{n}{4}) + 2^{3*log_2n}$

= $64T(\frac{n}{4}) + 2^{log_2n^3}$

= $64T(\frac{n}{4}) + n^3$

$T(n) = a T(\frac{n}{b}) + \theta(n^klog^pn)$

Here, $p = 0$ and $a = b^k => 64 = 4 ^3 $ and $p\gt -1 $

$T(n) = \theta(n^{log_ba} log^{p+1}n)$

$T(n) = \theta(n^{log_464}log^1n)$

$T(n) = \theta(n^3log n)$

---

here my answer correct if i m wrong

---

easy explaination @Neha Poddar

Answer 2

Ans => C

Using master method we solve this problem

A=64 and B=4 and 64 also write as 4^3 

So n^(logb a) become n^3 and

f(n) = 8^(log2 n) we interchange value 8 and n then it become n^(log2 8) => 3 mean n^3 

by master theorem second rule we add logn in f(n) then it become n^3logn

 

Corrrect me if i am wrong😅

Answer 3

Step 1: Simplify $f(n)$

Using the logarithmic identity $x^{\log_y z} = z^{\log_y x}$:

 

$$f(n) = 8^{\log_2 n} = n^{\log_2 8} = n^3$$

Step 2: Identify Parameters

• $a = 64$

• $b = 4$

• $f(n) = n^3$

Step 3: Compare $f(n)$ to $n^{\log_b a}$

$$n^{\log_b a} = n^{\log_4 64} = n^3$$

Step 4: Apply Case 2 of the Master Theorem

Since $f(n) = \Theta(n^{\log_b a})$, we fall into Case 2:

 

$$T(n) = \Theta(n^{\log_b a} \log n)$$

$$T(n) = \Theta(n^3 \log n)$$

Correct Answer: C. $\Theta(n^3 \log n)$