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.