The complete graph $K_n$ is the graph with $n$ vertices where any two vertices are connected by an edge.
The complete bipartite graph $K_{n,n}$ is the graph with $2n$ vertices which can be partitioned into two subsets $V_1$ and $V_2$ of size $n$ such that any two vertices $a\in V_i$, $b\in V_j$, are connected by an edge if and only if $i\neq j$.
Let $m\geq 1$ be arbitrarily large.
What is the minimum value $f(m)$ such that any graph with $m$ vertices and at least $f(m)$ edges contains $K_n$ as a subgraph?
What is the minimum value $g(m)$ such that any graph with $m$ vertices and at least $g(m)$ edges contains $K_{n,n}$ as a subgraph?
I am particularly interested in the order ($O(f)$, $O(g)$, $o(f)$, $o(g)$) of the functions $f$ and $g$, and whether it is quadratic or linear.
Some observations:
${{n}\choose{2}} \leq f(m) \leq {{m}\choose{2}}$.
$n^2 \leq g(m) \leq {{m}\choose{2}}$.
$g(n)\leq f(2n)$.
$f(m) \leq {{m}\choose{2}} - (m-n+1) + 1 = \frac{m^2}{2} - \frac{3m}{2} +n$.
To see that the last observation holds let's pick a graph $G=(V,E)$ of size $m$ with no $K_n$ subgraph. We show that $|E|\leq {{m}\choose{2}} - (m-n+1)$.
Pick a subset $V_1$ of $n$ vertices and then fix an edge $e_1$ between vertices in $V_1$ that is not in $E$ (by assumption it always exists). Then create $V_2 \subseteq V$ by taking away one of the two vertices connected by $e_1$, which we denote $a_1$, and adding a new vertex from $V \setminus V_1$. We repeat the process to find a missing edge $e_2$ in the subgraph induced by $V_2$ and create $V_3$ by erasing a vertex $a_2$ connected by $e_2$ and adding a new vertex in $V\setminus (V_2 \cup \{a_1\})$. We repeat the process and end up with $m-n+1$ missing vertices in $G$, namely $e_1, e_2, \ldots$.