The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to the conclusion that we're basically solving the recurrence $T(n) = T(n/3)$ and $T(n) = T(n/7)$, but I don't understand how to prove their big-$O$ form. How do we typically go about proving the upper bound? My instructor says that creating a tree and summing the branches is an acceptable first step, but it doesn't serve to prove the correctness of the upper bound.
Are there any methods that can help me see the recurrence relation more intuitively in general?
You are missing a factor $c$ on the $n$ in the first recurrence, but that doesn't matter for $O$. You are missing a term in your other recurrences. In the first one, the $T(n/5)$, which comes from $T(2n/10)$ is from finding the true median of the medians of groups of five. It is reasonable to replace that with $T(n/3)$ or $T(n/7)$. The second term is from finding the median of what is left. You need to assess the worst case of how many elements will be eliminated if you pick the worst pivot. That replaces the $T(7n/10)$ because in the subgroup of $5$ you are guaranteed to eliminate $3/10$ of the elements.