# What is best case and worst case for this algorithm?

I am supposed to create an algorithm for this statement: “Two input lists of size n have at least one element in common”

This is my algorithm:

bool func(L1, L2){
val1, val2 = 0;
for(int i=0; i<n; i++){
val1=L1[i];
for(int j=0; j<n; j++){
val2 = L2[j];
if(val2 = val1){
return true;
}
}
}
return false;
}


I know that you use big-theta notation to solve it, but my problem is on how to get the equation T(n).

This is what I did: first statement executes n times, 2nd → n times, 3rd → n 3 times etc, and got 3n^3 + 2n + 3, which I am sure is wrong...

Once you find the equation, how do you find the best and worst case from it? And how do you even find the equation?

BTW, don't tell me to read this site or book or smth cause I am asking only after doing all that. I need direct help. Not hints. Thanks!

• "I am supposed to create an algorithm for this statement: “Two input lists of size n have at least one element in common”" -- I have no idea what that's supposed to mean. "I know that you use big-theta notation to solve it" -- this, neither. What does "solve [an algorithm]" mean? Be precise! – Raphael Jul 16 '17 at 10:24
• "BTW, don't tell me to read this site or book or smth cause I am asking only after doing all that. I need direct help. Not hints." -- That's not the most helpful mindset. – Raphael Jul 16 '17 at 10:25
• Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! – Raphael Jul 16 '17 at 10:26
• The best case should be really obvious: When both elements have the same first element. On the other hand, your last sentence seems to indicate a unwillingness to learn. I'll tell you this, if I wasn't willing to learn all the time, I'd have been out of a job for the last 30 years. – gnasher729 Jul 16 '17 at 11:58

• It is not completely trivial to compare $L_1$ and $L_2$ in $O(n)$ – binary search takes $O(n\log n)$ time. You can get $O(n)$ if you merge the lists carefully. – Yuval Filmus Jul 16 '17 at 19:49