I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it?
$$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad &\text{ if n>1} \end{cases}$$
On
Let $S(n)=T^2(n)$ Then the recurrence is $S(n)=\frac 12(S(n-1)+S(n-2))+n$ gives $S(n)=\frac 13n^2+\frac {15}{27}n+\frac 2{27}-\frac 2{27\cdot 2^n}$
Hint: Let $a(n)=T^2(n)$. Then the recurrence relation becomes
$$a(n)={1\over2}a(n-1)+{1\over2}a(n-2)+n$$
with $a(0)=0$ and $a(n)=1$. Now try finding $c$ and $C$ for which there's an inductive proof that $cn^2\lt a(n)\lt Cn^2$ for sufficiently large $n$.
Added later (at OP's request): I'll do one inequality, which hopefully will show you how to do the other.
We'd like to find a constant $C$ such that $a(n-1)\lt C(n-1)^2$ and $a(n-2)\lt C(n-2)^2$ together imply $a(n)\lt Cn^2$. If we just plug the assumed inequalities into what we know, we have
$$\begin{align} a(n)&={1\over2}a(n-1)+{1\over2}a(n-2)+n\\ &\lt {1\over2}C(n-1)^2+{1\over2}C(n-2)^2+n\\ &={1\over2}C\big(n^2-2n+1+n^2-4n+4\big)+n\\ &=Cn^2+(1-3C)n+{5\over2}C \end{align}$$
Keep in mind that this is all "scratch" work: We're not writing up a proof at this point, nor are we trying to find the exact value of $C$ that gives the inequality, we're just trying to spot a value that will make things work.
The key is in the coefficient $(1-3C)$ in the last line. If $C$ is big, that coefficient is negative, which will make the term $(1-3C)n$ hugely negative if $n$ is "sufficiently" large. So let's pick a convenient value and see what happens. Let's try $C=2$.
If you redo the derivation above with $C=2$, you wind up with
$$a(n)\lt 2n^2-5n+5\lt 2n^2\quad\text{if }n\ge2$$
since $5-5n$ is negative for $n\ge2$.
Note that any $C$ greater than ${1\over3}$ will make $1-3C$ negative, so you don't have to choose $C=2$. It just happens to be convenient. Something similar should happen when you look at the other inequality, $cn^2\lt a(n)$. Give it a try!