'look' can stop working when it finishes the sorted section of 'dog', whereas grep must continue to the end of the file. Ignoring memory hierarchy, naturally '

'look' can stop working when it finishes the sorted section of 'dog', whereas grep must continue to the end of the file. Ignoring memory hierarchy, naturally 'look' would be O(log n) while grep would be O(n). Special input (sorted in this case) of course often calls for matching algorithms, when speed matters.