0


T(n) is the running time of an algorithm of input size n. The algorithm solves the problem by breaing it up into 4 problems of the same kind (I take "same kind" to mean we're going to use function T) each of size n/4 . The solution to the original problem is obtained by combining the 4 sub problems in time n (What does this mean in the context of the recurrnce relation ?). Express T(n) as a recurrence relation and derive an expression for T(n) in terms of n , Assume T(1) = 2 .

What i have done

I came up with T(n) = 4T(n/4)

but I'm really unsure as to what to do next. I would appreciate any guidance, thank you.

FutureSci
  • 247
  • 2
  • 9
  • If someone could guide me to a good resource where-in i could learn this topic in depth , i would be grateful. Thank you. – FutureSci Apr 05 '17 at 05:35
  • 1
    I think the relation is $T(n) = 4T(n/4)+n$, where the $+n$ is the cost of combining the output of the four subproblems. – angryavian Apr 05 '17 at 05:40
  • I was thinking something like that, but T(n) = 4T(n/4) + c , for some constant c . I don't think it'll be n. If im not mistaken . – FutureSci Apr 05 '17 at 06:02
  • 1
    That is how I was interpreting the "combining ... in time $n$" part of the problem statement. – angryavian Apr 05 '17 at 06:47

0 Answers0