2

I'm really getting frustrated about solving the Recurrence above. I was trying to solve it by using the Master Method, but I just didn't get it done...

I'm having a recursive algorithm that takes 3log n times (three binary searches) to identify four sub-problems, each with with a size of n/4, and then solves them individually until n is smaller than some constant given by input. So I got this recurrence as a result:

T(n) = 4*T(n/4) + 3*log(n)

Base-Case if n < c (c = some constant given by program input):

T(n) = 1

I'm trying to find the asymptotic running time of my recursive program, and wanted to solve it by using the master theorem. Can anybody tell me if it's possible to use the master theorem with this recurrence, and if yes, which case of the master theorem is it?

All help is appreciated, thanks.

5
  • 2
    your question is very elusive; I have a hard time understanding what you are trying to achieve, what has not worked or what you tried for that matter. Please be a bit more explicit. Some code samples would help to!
    – Pandrei
    Mar 2, 2015 at 16:49
  • 1
    @Pandrei I want to analyse the running time of my recursive algorithm and wanted to know if you can solve this recursive recurrence by using the master theorem, and if I can use it, how I can solve the recurrence. Mar 2, 2015 at 16:57
  • @ChristophGerl the master theorem allows you to calculate the running time of a recursive algorithm by using the big O notation. What do you mean solve the recurrence?
    – Pandrei
    Mar 2, 2015 at 17:03
  • @Pandrei Oh well, sorry I made a mistake there... Sure, I want to find my Algorithm's running time in terms of the Big O notation. I thought you also call it "to solve the recurrence" because T(n) is the recurrence. Mar 2, 2015 at 17:06
  • When you start getting into questions that involve more 'sciency' than 'programmery' aspects (the master theorem and asymptotic complexity) you may find that cs.stackexchange would be able to give a more in depth answer.
    – user289086
    Mar 9, 2015 at 18:25

1 Answer 1

3

T(n) = O(n), because a logarithm of 4 base 4 is 1 and 3 * log(n) is O(n ^ 0.5)(0.5 < 1). It corresponds to the first case of the Master theorem as described here.

1
  • Thanks a lot. I thought the constant of n^c need to be an Integer. Mar 2, 2015 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.