4 ms·
Would the optimal solution be O(n*log(m)), where n is the number of IP addresses in list one and m is the number of IP addresses in list 2?
by AdamTReineke 15y ago
Would the optimal solution be O(n*log(m)), where n is the number of IP addresses in list one and m is the number of IP addresses in list 2?
- deleted 15y ago[deleted]
- kenjackson 15y agoI think O(n * 2^p) is also a possibility, where p is the number of slots in the address. For standard IP addresses p is 4. So for large m, this might be preferable. I'm basically just hashing values to get this. How do you get the log(m) factor?
- gordonguthrie 15y agoIf it is a long list then the O of the algorithm matters a lot. If its a short list, who cares? If you care about it all the time then you a premature optimiser - basically a hand-grenade with the pin out. (by you I mean 'one' here - not you AdamT)
- eru 15y agoIf you are implementing, than you are right. If you are interested in studying algorithms and how they work, asymptotic considerations can tell you a lot about the algorithm. You have to decide what you want to ask for in your interview.