Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
#136, Space complexity
#1
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);
           }
       }

  1. θ(n2)

  2. θ(n)

  3. θ(logn))

  4. θ(nn)

  5. θ(1)

  6. θ(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.
Reply
#2
You are correct. The correct answer should be theta(log x).
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)