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);

}

}

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)