Complexity...

TEJAS JOSHI

unread,

Feb 8, 2010, 10:34:40 PM2/8/10

to VANI_GATE_CS_2010

T(n) = 1 for n<=5

=T(n/5)+T(3n/4)+n for n>5

which is true

(A) T(n) = theta (n^2)
(B) T(n) = omega (root n)
(C) T(n) = theta (n)
(D) T(n) = theta (n log n)

Varun Shinde

unread,

Feb 9, 2010, 12:27:25 AM2/9/10

to VANI_GATE_CS_2010

Answer is C. theta(n)

TEJAS JOSHI

unread,

Feb 9, 2010, 3:19:13 AM2/9/10

to VANI_GATE_CS_2010

can u explain the procedure........

Varun Shinde

unread,

Feb 9, 2010, 3:53:39 AM2/9/10

to VANI_GATE_CS_2010

In above equation T(n)=T(1) for n>=5 so according to definition of
Big Oh notation
T(n)=O(1) for all n>=n0 where n0=5

harshjpathak

unread,

Feb 10, 2010, 3:14:58 AM2/10/10

to vani_gat...@googlegroups.com

here you will need to use the recursion tree method. We divide n into two subproblems one of size n/5 and other of size 3n/4. Again each of n/5 is divided into 3/10 and 9n/16. Then we just do an induction on the height of the tree. At the max height cost of each subproblem will be T(1). You will need mathematics for this. Approach is given in cormen book in chapter of recurrences. It will be difficult to explain it here as it is not possible to represent diagrammatically.

harshjpathak

unread,

Feb 10, 2010, 6:41:39 AM2/10/10

to vani_gat...@googlegroups.com

From did u get the question?. I think either it should be n/4 or 3n/5. We are dividing the problem into subproblems so their addition must be n. Please check and let me know if im wrong

Reply all

Reply to author

Forward