• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 #136, Space complexity etberryhill Junior Member Posts: 14 Threads: 6 Joined: Aug 2017 Reputation: 0 09-04-2017, 06:01 PM What is the space complexity of this function? Assume positive, integral input and integer division.    function f(x,n)        {        if (x > 0)            {            f(x/2,n);            for (var i from 0 until n)                println(n);            }        } θ(n2) θ(n) θ(logn)) θ(n√n) θ(1) θ(nlogn) Since we are talking about space complexity here, wouldn't the answer need to be in terms of x in this question? Since the recursive case is evaluating x against 0 and there is log(x) recursions that need to store a constant amount of data on the stack, you have log(x) recursions * constant amount of data = log(x) space complexity. lusth Administrator Posts: 316 Threads: 23 Joined: Jul 2017 Reputation: 15 09-04-2017, 09:31 PM You are correct. The correct answer should be theta(log x). « Next Oldest | Next Newest »

Forum Jump:

Users browsing this thread: 1 Guest(s)