The recurrence relation
T(1) = 2
T(n) = 3T (n/4) + n has the solution T(n) equal to

O(n)

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

O(logn)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

O(n3/4)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

none of these

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A O(n)
The recurrence relation

T(1) = 2

T(n) = 3T (n/4) + n has the solution T(n) equal to

Suggest Corrections

Similar questions

\frac{n}{2}

\sqrt{n}

\geq

T (n) = 2 T (\frac{n}{2}) + \frac{n}{l o g n} i s

2^{2 k}

\geq

\sqrt{2}

\sqrt{n}

T (n) = 4 T (\sqrt{n}) + l o g^{2} n

Join BYJU'S Learning Program