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!