关于Big O(n)噪声下数据库可重构性的技术疑问

已知背景 #

• 公然非私有算法定义：若敌手能构造数据库c∈{0,1}^n，使其与真实数据库d仅o(n)个条目不同，则该算法为公然非私有。
• 定理2结论：若分析师可发起2n个子集查询，且管理员添加的噪声有界为E，那么敌手可重构除4E个位置外的数据库。

核心困惑 #

当作者指出噪声界E=O(n)时，敌手可基本重构整个数据库，我完全无法理解：根据Big O的定义，O(n)意味着E的量级与n相当，那么4E应该是一个和n同量级的大数值，按照定理2的结论，应该有大量位置无法重构，为何反而能基本重构整个数据库？

我查阅资料、询问他人均未得到解答。

内容的提问来源于stack exchange，提问作者hamza -