GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
271 views
I've been struggling to come to exact solution for this. Master's theorem is not applicable and likely way to get to answer is Recursion tree. Which is giving me Theta(n) as an answer.

Steps : =>

1)  T(n) = 2T(n/4) + √3

2) Emerging Pattern => (1/2^k) * n

3) Considering when we break down to T(1) : :   (1/2^k) * n  =1

4) k = log (n)

5) Each level has 2^i nodes :: 2^(log (n)) :=> n

6) If you sum up cost , n + n/2 + n/4 + ..... = n/2

Which is incorrect ,

Answer given is ( √n log n ) , would appreciate if someone could shed light how so ?
asked in Algorithms by Junior (769 points)   | 271 views
why masters theorem not applicable
Case (III) Regularity condition fails.
It is not case 3.  It is Case 1     $\sqrt {3}$ =$O(n^{1/2 - e})$
My bad , it is case (I) , but then  √3 =O(n1/2−e) does not always hold , so is it still valid ?

 

And , if you apply considering it does hold , answer given is ( √n log n ) and master's theorem would gives us √n .

2 Answers

+3 votes
Adding cost of each level;

$\begin{align*} T(n) &= 2^0.\sqrt{3} + 2^1.\sqrt{3} + 2^2.\sqrt{3} + .... + 2^{\log_4 n}.\sqrt{3} \\ &= \sqrt{3}.\left [ \frac{2^{\log_4 {n}+1}-1}{2-1} \right ] \\ &= \sqrt{3}.O(n^{\frac{1}{2}}) \\ &= O(\sqrt{n}) \end{align*}$
answered by Veteran (50.9k points)  

This is right , I was summing up thinking it's √3n ; anyways I'm not able to figure out  if √n * log n is wrong answer then ? 

+3 votes

In these type of questions where master method doesnt apply you can do the following

$T(n) = 2T(n/4) + \sqrt{3}$

Reframe it like this, by putting i in the specified positions

$T(n) = 2^{i}T(n/4^{i}) + i\sqrt{3}$

Now for n/4i = 1, put i = log4n

So the equation becomes

$T(n) = 2^{log_{4}n} + log_{4}n\sqrt{3}$

Or

$T(n) = n^{log_{4}2} + log_{4}n\sqrt{3}$

$T(n) = \sqrt{n} + log_{4}n\sqrt{3}$

And therefore

$T(n) = O(\sqrt{n})$

answered by Junior (889 points)  

Related questions

+2 votes
2 answers
1
0 votes
1 answer
2
asked in Algorithms by iarnav Active (2.2k points)   | 88 views


Top Users Aug 2017
  1. ABKUNDAN

    4654 Points

  2. Bikram

    4032 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2856 Points

  5. manu00x

    2664 Points

  6. makhdoom ghaya

    2380 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1756 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,878 questions
31,952 answers
74,104 comments
30,065 users