please help me on this

The Gateway to Computer Science Excellence

0 votes

T(n) = T(n/4) + T(3n/4) + n

How to solve these type of problems?

Can I solve this using master theorm by considering X = T(3N/4) +N THEN

T(N) = T(N/4) +X

CAN WE SOLVE LIKE THIS?

PLEASE HELP

How to solve these type of problems?

Can I solve this using master theorm by considering X = T(3N/4) +N THEN

T(N) = T(N/4) +X

CAN WE SOLVE LIKE THIS?

PLEASE HELP

0

no brother you have to consider both the function to get the result though only one side can be considered either to find best case time or worst case time.

0

Then how do we tackle these type of problems?

can you please provide easy way to solve these

Thanks

0

bro see which one is big and we merge smaller one into it means we ignore it simply......

T(n) = T( 3n/4) + n

T(n) = T( 3n/4) + n

+1

brother use recursive tree method when there is more than one function...

and go with basics it will help you to reduce it to simple methods.

refer this : https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html

0

Hey @arvin , in the second example of the below site (*T(n) = T(n/3) + T(2n/3) + n*.)

https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html

how we came to know that size of the tree is *log3/2 n ??*

0

@Nandkishor3939 till T(1)=T(n/(3/2)^k) means n/(3/2)^k= 1 simplify this and you will get k = log(3/2)n and it will be the longest path and n/(3)^k will be the shortest path k= log3n...

0

you can use that also but it will give Ω(nlog3n).. because the length of chain will be small as compared to T(2n/3)

0

If you solve the rec reln by traditional method(by substitution and not by tree method)

you will see that T(n/(3/2)) will be like T(n/(3/2)^k) for k th transaction ....

so substitute T(1)=T(n/(3/2)^k) because we need to kind value of k such that we will reach the last stage of recurrence relation i.e. T(1)

thus we will get an idea of how deep the tree(it is quite intuitive !) will be (that's what the discussion was all about)

you will see that T(n/(3/2)) will be like T(n/(3/2)^k) for k th transaction ....

so substitute T(1)=T(n/(3/2)^k) because we need to kind value of k such that we will reach the last stage of recurrence relation i.e. T(1)

thus we will get an idea of how deep the tree(it is quite intuitive !) will be (that's what the discussion was all about)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,709 answers

199,417 comments

107,623 users