This ought to be simple right? 

My very first thought is that we are potentially looking at every string to find the right one. So it is O(N). But wait. For each string we loop through each character of that string. We got two loops. So maybe it is O(N^2) ?

But lets think about this more carefully. Each loop is looping over different kinds of data. The outer loop are strings while the inner loop are characters. So why no use the same units everywhere? Meaning let’s look only at the characters. How many character comparisons do we have to do?

Say the string list contains a total of N characters. The string we are searching for is made up of M characters.
Consider a worst case. Every string in list are the same as the search string except the last character. The string list then contains N/M strings. That is, each string is M characters long. How many comparisons do we do? For each of the N/M strings we do M comparisons. That totals (N/M)*M = N comparisons.  So it is linear. Really? How can that be, we have to go trough every character in the search word multiple times. We got two loops. How can it not be O(N^2)?

The key observation is that in the string list we are never looking at a character twice. If we only look at the number of comparisons we do in total. We don’t do more than N comparisons between a character in the string list and a character in the search string.

Consider some of the other extremities. N = M, that is the search string contains as many characters as there are characters in the string list in total. And say the string list only contains one string. Obviously its is O(N) comparisons. At the opposite extremety each string in the string list is only 1 character. We compare with N strings, but for each of these comparisons M - 1 characters in the search string will never be visited. 

This example illustrates that when considering big O it is not enough to merely look at the number of loops nested inside each other. One has to think about what are exactly the elements which are being processed.