We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$.
How to show that $T(n) = O(n \log n)$?
Basically, if we look at the tree of function calls, the longest path is done by calling to $T(0.75)$ again and again. The length of this path is $\log_{4/3} n$. Since every call is $O(n)$ we may conclude that $T(n) = O(n \log n)$.
I think my answer is pretty much right, but maybe not rigorous enough. I'd be glad if you could help me formalize it, or alternatively suggest another way to do it.
I've understood that induction may be used, but I've never done it before so I'd be glad if you could explain the process of proving it by induction.
A comment: saying "for $n \leq 100$, $T(n) \in O(1)$" is redundant. $T$ will be bounded on bounded sets by definition.
Anyway, you have the right intuition. A fast, rigorous answer to your question comes from the Akra-Bazzi method. Using Wikipedia's notation we have
$$g(x) = x \\ a_1=a_2=1 \\ b_1=1/4,b_2=3/4 \\ h=\text{ a correction for non-integer indices, which is never larger than } 1.$$
So we now need to find $p$ such that
$$\sum_{i=1}^2 a_i b_i^p = 1.$$
In this case this is easy, $p=1$. So the Akra-Bazzi method tells us that
$$T(x) \in \Theta \left ( x \left ( 1+\int_1^x \frac{u}{u^2} du \right ) \right ) = \Theta(x \log x).$$