1. if f(n)=O(n), what is the running time of the following recursive function?
function Recurse(A[1..n])
f1(n)
t1 <-- Recurse(A[1..(n-1)])
t2 <-- Recurse(A[(2..n])
return (t1+t2)
end function
2.
if f(n)=O(log n), what is the running time of the following recursive function ?
function Recurse(A[1..n])
f1(n)
m <-- n/3
t1 <-- Recurse(A[1..m])
t2 <-- Recurse(A[(m+1)..2m])
t3 <-- Recurse(A[(2m+1)..3m])
return (t1+t2+t3)/3
end function
please help me
Infinity for both functions.
Also, the functions are ill-typed.