CareerCup

No one asks these types of questions in interviews. We are not in college.
Please take your homework elsewhere.

When in doubt, Wolfram Alpha is the one to help you out.
Go to : wolframalpha.com/input/?i=T(n)+%3D+n+*+(+T(n%2F2)+%5E++2+)
You are correct, it is exponential in nature :
picpaste.com/w38Ckgj7.png

Clearly now, it has tight asymptotic bound is it not?

O( (N/2)^(N-1) )

Actually, one can use logarithmic series to solve this problem.
Check this out

T(n) = n(T(n/2)^2)
Log(T(n)) = Log(n(T(n/2)^2)) => Log(n) + 2Log(T(n/2))
Log(T(n)) = Log(n) + 2(Log(n/2) + 2Log(T(n/4)) and so on which you can write as
Log(T(n)) = Sum(i = 0 to k)(2^i * Log(n/2^i) where k is Log(n)

Now, If you see the values of this sequence varies from Log(n) to n.
Worst case would be that the sum is nLog(n) only, considering every value to n, and i varies from 0 to Log(n), so that sum.

Log(T(n)) = nLog(n)
T(n) = 2^(nLog(n)) = n2^n.

and so this does not have asymtotic bound.
Now we know that the sum would always be more than n, which itself make the

T(n) = 2^n

and so, this does not have any asymptotic lower bound, and so it does not have tight asympotatic bound.

T(n) = 4^(n-1)/n
Brute-force exact solution:

T(n) = n*(T(n/2)^2) 
ln(T(n)) = f(n) = 2*f(n/2) + ln(n)
f(2^x) = 2*f(2^(x-1)) + ln2*x
f(2^x) = g(x) = 2*g(x-1) + ln2*x
g(x) = h(x)*2^x  = 2*h(x-1)*2^(x-1) + ln2*x
h(x) = h(x-1) + ln2*x/2^x = ln2*(x/2^x + (x-1)/2^(x-1) +...) = ln2*(2 - (x+2)/2^x)
//
h(n) = 1/2+2/4 +3/8+...+n/2^n  = 2 - (n+2)/2^n
h1(x) = 1 + x/2 +...+ (x/2)^n = [1-(x/2)^(n+1)]/[1-(x/2)]
h(n) = h1'(x=1) = -2*[(n+1)*(1/2)^(n+1)] + 2*[1-(1/2)^(n+1)] = 2 - (n+2)/2^n
//
g(x) = ln2*(2 - (x+2)/2^x)*2^x = ln2*(2^(x+1) - (x+2))
--check: ln2*(2^(x+1) - (x+2)) = 2*ln2*(2^x - (x+1)) + ln2*x : OK!!
f(x) = f(2^lg2(x)) = g(lg2(x)) = ln2*(2*x - (lg2(x)+2))
T(n) = exp(ln2*(2*n - (lg2(n)+2))) = 2^(2*n - (lg2(n)+2)) = 4^(n-1)/n
--check: 4^(n-1)/n = n*(4^(n/2-1)/(n/2))^2 = 4*n*4^(n-2)/n^2 ...OK!