How do you find set of keywords present in set of words in linear time or log time?
I'm interpreting your question as wanting to quickly ensure that every word from the keys list is included in the sentence list.

Assuming you're using a sane version of python, the running time for the initial construction of the counter object is linear in the length of the sentence's description. At least as long as no word appears so many times that the integer stored in the counter exceeds INT_MAX.

So the overall running time, for sane inputs, is linear in the input, which is the best you can possibly expect (since Python has to read the entire input anyway, which takes linear time already).

That said, there's no compelling reason to use a counter here. You could just as easily have used a Set object and achieved the same running time without the assumption on word counts not exceeding a certain value. It might also be easier to read.

For example

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    for key in keys:
        if key not in sentence_word_set:
            return False
    return True


or even

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    return all(i in sentence_word_set for i in keys)


Set construction is promised to be expected linear-time in the size of sentence, with expected constant-time lookups. And the for loop goes through each key once (totalling to something linear in the size of keys) so the running time is expected linear in the whole input. Which again is the best you can do.