Having trouble understanding blatantly non-private definition because of Little-o notation
The interpretation of your professor is &quot;intuitively correct&quot; (but still formally wrong).
The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$.
That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a vanishingly small fraction of the entries.
Notice that if $c$ agrees with $d$ &quot;only&quot; on $99.9\%$ of the $n$  entries, then the number of disagreements still grows linearly with $n$. Indeed: $0.001n \in \Theta(n)$ and hence $0.001n \not\in o(n)$. See the page about asymptotic notation on Wikipedia.