103 views

Hey guys ignore the options. What will be the answer by solving the relation?

more appropriate O(qn).

since p and q are constant ...q can have maximum constant value can go upto n....so the second part of the recurrence will give higher order .

so the order can be n^n(option b)

we can apply master theoram

a=8 b=2

k=0

a>b^k

so TC= O(n^3)
You'r doing it wrong.
Why didn't you considered term $q^n$.

Let, q = 2;

then, $T(n) = 8*T(\frac{n}{2}) + 2^n$, which is upper-bounded by $n^n$ only.

Should not option is O(qn). since we dont take heigher value for big-oh.

question is wrong . If it was qn inplace of qn, then C is right .

otherwise O( qn) is more appropriate.

Agree O( 2n) is far far less than O(nn) .