Not sure if I completely understand this problem that was presented in class. We were given function $$f(n) = 2*f(n-1) + n$$ The base case for all these functions $f(1)$ is equal to 1. Assume $T(x)$ is equal to the running time of $f(x)$. Recurrence of this algorithm is solved as $$T(n) = T(n-1) + 1$$

This is bounded by $$T(n) = \theta(n)$$

I thought this was the time complexity, but then we were given that the time complexity, where time complexity = $TC(r)$, in relation to the size of the data is: $$TC(r)=\theta(2^r)$$ I read somewhere this has to do with bits possibly, but I'm not sure how they got to this bound. Space complexity, where space complexity = $SC(r)$ was also given as: $$SC(r)=\theta(2^r)$$

  • 3
    $\begingroup$ "Assume $T(x)$ is equal to the running time of $f(x)$." Did the exercise really say that? It doesn't make sense. $f$ is just a mathematical function: a mapping from natural numbers to natural numbers. Functions don't have time complexity: time complexity is a property of computational problems, not mathematical functions. $\endgroup$ – David Richerby Nov 22 '15 at 22:23
  • $\begingroup$ It's possible it was $T(n)$ instead of $T(x)$. $\endgroup$ – Jakub Kawalec Nov 22 '15 at 22:50
  • 2
    $\begingroup$ Sure, but it wasn't the name of the variable that was bothering me. Asking what is the time complexity of a mathematical function is a category error, like asking what is the colour of a word (it depends on what colour ink you use to write it). $\endgroup$ – David Richerby Nov 22 '15 at 23:03
  • 2
    $\begingroup$ The recurrence is wrong in any case: no way does it solve to the runtime function. One has to ask a different question resp. look more closely to see why is makes sense. (cc @DavidRicherby) I recommend to check out our reference questions. $\endgroup$ – Raphael Nov 22 '15 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.