The heuristic for this, FWIW, is to think about reducing the number of things you're messing with (such as a search set) by a factor (usually 2, not always) on every iteration. A binary search is a logarithmic algorithm because you chop off half of the (sorted) search set on every pass. That's all you really need to know about it to identify one (and thus realize you have a sublinear-time algorithm).

You don't need to read a ton of books or know any math at all really - the basic answers they are typically looking for are patterns you can spot with no knowledge of logarithms what so ever.

Spend a few days and you will just recognise, "oh hey I've a nested loop here, it's likely O(n2)!" That's really all it takes, and there are only 4-5 main classifications most interview code falls into, all of which can be spotted without knowing what a logarithm is. If I had interviewed you, I would not be impressed you hadn't understood this at such a basic level either, personally. The rest of us making a full time living at software engineering have to learn it to pass interviews at top companies too!