Optimization issue in Python

Question

TASK:
Take an integer named n from user. Take n times name-phone number input from user then take names again. If names that you entered second time is in the list print name=phone number related. Else print Not found.

Example input:

input_example

Example output:

enter image description here

The problem is that I wrote a working code. But if you pass to n a value that is too big, the code takes too much time to solve it. It's a challenge question so website that I'm working on doesn't accept my code and wants me to optimize the code. I tried a few different ways to optimize it however none of them solved that issue.

My Code:

n = int(input())
d = {}
for x in range(n):
 key_value = input().split()
 d[key_value[0]]= key_value[1]
 
lofnames = []
for name in range(n):
 name = input()
 lofnames.append(name)
for name in lofnames:
 flag = False
 for key in d:
 if key == name:
 print(f"{key}={d[key]}")
 flag = True
 if flag == False:
 print("Not found")

• Totem: If n is a very large number, and you're timing out, perhaps you could find a way to cut down on the number of loops in your code, or things you do in those loops. Google around for optimising python for speed, I know there are helpful pages out there, I've found them :b
• BooRuleDie: I tried to add break under the flag = True, but it didn't work =( .

Answer 1

It looks like your function's runtime complexity is O(N^2) and not O(N) as the site probably wants it to be, due to the nested for loop you have. You can cut down on this complexity by not iterating through the dictionary and instead using its property as a hashtable of an O(1) lookup time. Consider using a try-except block to except KeyErrors in the dictionary for the key name that you're looking for.

Answer 2

You're manually iterating over the dictionary's keys, performing an O(n) operation for each name that you want to check. You could just use the in operator to check for a name's existence in an O(1) operation:

for name in lofnames:
 if name in d:
 print(f"{key}={d[key]}")
 else:
 print("Not found")

• BooRuleDie: Thank you helped a lot!