Having trouble understanding blatantly non-private definition because of Little-o notation

Question

I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.

Definition 8.1.A mechanism is blatantly non-private if an adversary can construct a candidate database 'c' that agrees with the real database 'd' in all but o(n) entries, i.e.,‖c−d‖0∈o(n).

A bit of context. 'd' is a database where each row is one individual 'i' with 'n' individuals in total. the database has just one column representing some important questions. The values of the column can be 0 or 1. 'c' is a candidate database, a database that will try to be as similar as possible to the database 'd', it has the same structure one row for each individual and values for the column of {0,1}. Both are treated as a vector.

I watched a lecture and the informal description of the professor was "database 'c' will agree with database 'd' in 99,9..% of the cases".

But my interpretation of the definition is exactly the opposite "database 'c' will agree with database 'd' in all entries except 99,9..%".

My definition seems a bit odd to a "blantly" non-private mechanism. But I cannot understand how "except o(n)" would mean that a minority of the entries would not be equal in both databases.

Answer 1

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.