Time Complexity:
O(n^2)
In this next scenario, let’s say that only one person knows who took your cookie and only by name. The person who took the cookie won’t fess up to it either, so you have to name off each other friend to the friend you are talking to. This can be written in Python3:
>>> def who_has_my_cookie(my_friends):
... for friend in my_friends:
... for their_friend in friend.get('friends'):
... if their_friend.get('has_cookie'):
... return their_friend.get('name')
If you imagine yourself in this situation you can see that it’s going to take a lot longer than any of the other situations because you need to keep reciting everyone’s name every time you go to the next friend.Worst case scenario, you need to cycle through each friend and ask them about every other friend. If you look at the loops, you can see that the outer loop has a time complexity of O(n), and the inner loop also has a time complexity of O(n). This means the function will have a time complexity of O(n^2) because you multiply the time complexities together O(n * n).
Let’s feed this function some input and see who took your cookie:
>>> my_friends = [
... {'name':'Steven', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Binita', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Linds', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Raman', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':False},
... {'name':'Elaine', 'has_cookie':False}
... ]
... },
... {'name':'Elaine', 'friends':[
... {'name':'Steven', 'has_cookie':False},
... {'name':'Binita', 'has_cookie':False},
... {'name':'Linds', 'has_cookie':False},
... {'name':'Raman', 'has_cookie':True},
... {'name':'Elaine', 'has_cookie':False}
... ]
... }
... ]
>>> cookie_taker = who_has_my_cookie(my_friends)
>>> print(cookie_taker)
Raman
Summary of O(n^2): There is a loop within a loop, so you could instantly think that it would be O(n^2). That’s a correct assumption, but to make sure, double check and make sure the increments are still being incremented ntimes. Some loops within loops turn out to be O(nlog(n)).