1
$\begingroup$

I have an algorithm broken down into the pseudish code below. But the gist of it is, we go through every person in a list, we then ask them to talk to all of their friends. Every time we choose a person to eval in the list, it costs $log N$ time. Every time that person talks to a friend it costs $log N$. What is the time complexity? Is my answer right?

My answer: $O(N \cdot log(E \cdot log(N)))$

List[People] // N

forall People in List:  //O(Log N) to get a person in list
   forall friends of Person:    // Person has a set of Friends E that is [0, N) 
       Person.talkToFriend(friend)  //Costs O[LogN] to talk to a friend
$\endgroup$
1
$\begingroup$

For each of the n people in the list you do $|E|\cdot log(n)$ plus the time of getting it from the list, which is $log(n)$. So the time you start with is complexity: $O(n(log(n)+(log(n)|\cdot|E|)))=O(n\cdot|E|\cdot log(n))$

Assuming E could be as big as n, you could simply say the time complexity is $O(log(n)\cdot n^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.