It is fairly elementary to align both equations, as well as their variable domains, when defining your own "cases environment" via an array:
\documentclass{article}
\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\begin{document}
\begin{align*}
T_{\text{in general}}\left(n\right) &= aT\left(\frac{n}{b}\right) + n^{c}, && a\geq 1, b\geq 1, c>0 \\
& && a>b^{c} \\
T_{\text{cases}}\left(n\right) &=
\smash{\left\{\begin{array}{@{}l@{}}
\Theta\left(n^{\log_{b}a}\right) \\[\jot]
\Theta\left(n^{c}\log_{b}n\right) \\[\jot]
\Theta\left(n^{c}\right)
\end{array}\right.} && a=b^{c} \\
& && a<b^{c}
\end{align*}
\end{document}
Some minor alignment adjustments were made (like using additional & alignment specifiers), as well as \smashing the "cases environment" and adding the [\jot] line skip. \smash removed any vertical height from it's argument, while \jot is a specific 3pt skip provided by LaTeX.
From a typesetting point of view, note the use of \text{...} in the subscripts. This macro is offered by amsmath and allows text to be typeset in the regular way, while still adjusting for the relative size of the font depending on the placement.
