But don't declare "little N" too early. If N depends on user input for instance, there is a high chance it might turn out bigger than expected. There are even attacks that exploit worst case complexity of algorithms.
For example, using a balanced tree as a way to deal with collisions in hash tables is not necessarily a stupid idea. If the table is overloaded or because of a poor or easily exploited hash function, your hash map will degenerate into O(log(n)) instead of O(n).
Now if you know for sure that collisions are unlikely, for example because you control the data you put into it, that you know that it will never be larger than a certain size, and that your hash function is good, then you can assume N is small.
That's why, when I doubt, I always consider N large. Using a O(log(n)) container may be a bit less efficient for low N, but it will not become catastrophic if N becomes big. If performance is needed and there is no guarantee about N, hybrid approaches are best, and that's how good libraries tend to work.