This is a solution given by chegg a couple days ago for code in Python that when given an adjacency matrix for an aquaintance graph, find the celebrity(if there is one) by checking the fewest possible matrix entries. In this case a celebrity is a person who knows nobody but is known by everybody. I feel that the worst case effeciency of this code is n^2 when it could be more efficient (linear). What changes should be made to the provided code?

# If we go throuh one row, indexes which are 0, we know that those indexes will #never be Celebs( hence marking as NCelebs), only indexes which are l in that #row, have the possibility( hence marking as possibleCelebs) So we make a list of those possible celeb indexes for that row. (Checking beforehand that it was never visited before, and was not deemed to be a noCeleb once we visit an index we mark it as visited, so that in recursion we dont visit #it again. If it's all 0, we found the celeb. tif all possibleCelebs have been checked, and not was a celeb return-1 Helper Method Recurisve def findCelebRec(adjMatrix, curldx, numChecks,noCelebs,visited): possibleCelebs=[] celeb True visited[curldx] True for index in range (len(adjMatrix[curldx]) num Checks += 1 if adjMatrix[curldx[index]1: celeb False if(not(noCelebs[index and not(visited[index)): possibleCelebs.append(index) else noCelebs[index] True return [curldx,numChecks] result-findCelebRec(adjMatrix,idx.numChecks.noCelebs,visited) if celeb for idx in possibleCelebs: if(result[0]!-1): return result return-1,numChecks] def findCeleb(adjMatrix): noCelebs-[False]"len(adjMatrix[0] visited-False]* len(adjMatrix(01) return findCelebRec(adjMatrix,0,0,noCelebs,visited) adjMatrix ([0,0,1,1], [0,0,0,0], print findCeleb(adjMatrix))