Where's d image??

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

Correct answer is O(n log (base 4/5) n) so according to ans it would be O(n logn)

Here T(n) = O(n) + T(n/5) + T(4n/5)

T(n) = Cn+T(n/5)+T(4n/5) here

we will make recurrence tree between which will be between n/5 and 4n/5

and you will get n/(4n/5)^k = 1

k = log (base 4/5) n

so Cn* (log (base 4/5) n) = o(nlogn)

Here T(n) = O(n) + T(n/5) + T(4n/5)

T(n) = Cn+T(n/5)+T(4n/5) here

we will make recurrence tree between which will be between n/5 and 4n/5

and you will get n/(4n/5)^k = 1

k = log (base 4/5) n

so Cn* (log (base 4/5) n) = o(nlogn)

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 941
- Others 1.2k
- Admissions 334
- Exam Queries 410
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,234 questions

40,919 answers

116,193 comments

39,834 users