# What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say

"We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously hardcore bits. Next we introduce a new parameter regime for which we prove that the function family is still trapdoor one-way and has up to $N - o(N)$ simultaneously hardcore bits."

What are the authors trying to say about their new parameter regime? That's it's better or worse? I tried to graph $O(N/ \log_2(N))$ to see how it looks and I can see that the growth rate is slower than a linear function like O(N).

So $N-o(N)$ = something that is linear - something that grows slower than linear = something else that grows slower than linear. So the new parameter regime is better than $O(N/ \log_2(N))$ ?

I'm not sure I am following what they are trying to say.

• Why do you use the tag complex-analysis ? Sep 21, 2013 at 17:03
• sorry - I misread it to be complexity analysis. Sep 21, 2013 at 17:05

Every sequence in $N-o(N)$ is in $O(N)$ but not in $O(N/\log N)$.

Note that "something that is linear" minus "something that grows slower than linear" is "something else that grows" LINEAR, not "slower than linear". So the new parameter regime corresponds to sequences growing faster than those in $O(N/\log N)$.

• Thanks Did - So if the new parameter regime is worse then why do the authors write the paper? Whats the point? Sep 21, 2013 at 17:28
• The new parameter regime is better, not worse. It is more resistant to a class of attacks defined in the paper because the attack has to produce more bits of the key to break the cryptosystem.
– zyx
Sep 21, 2013 at 17:28
• Better/worse is set by the context of the paper, and there more is better. N - o(N) means the effective key size with and without the side attack is about the same. N/log(N) is a significantly smaller effective key size. This is what the 'hardcore bits' is intended to measure.
– zyx
Sep 21, 2013 at 17:45
• The authors say they "introduce a new parameter regime". This might mean the $O(N/\log N)$ previous result does not apply to this regime?
– Did
Sep 21, 2013 at 17:46
• In the new parameter regime, the scheme is more secure against the side attacks. That is the point of the paper.
– zyx
Sep 21, 2013 at 17:47