The interpretation of your professor is "intuitively correct" (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$ on "only" 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.

The interpretation of your professor is "intuitively correct" (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$ "only" 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.

The interpretation of your professor is "intuitively correct" (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 size 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$ "only" on 99.9% of the entries, then the number of disagreements still grows linearly with $n$. Indeed: $0.01n \in \Theta(n)$ and hence $0.01n \not\in o(n)$. See the page about asymptotic notation on Wikipedia.

The interpretation of your professor is "intuitively correct" (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$ on "only" 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.