-1
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ "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! $\endgroup$ – Raphael♦ Jul 16 '17 at 10:24
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael♦ Jul 16 '17 at 10:25
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael♦ Jul 16 '17 at 10:26
  • 2
    $\begingroup$ 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. $\endgroup$ – gnasher729 Jul 16 '17 at 11:58
1
$\begingroup$

The best case is when L1[0] = L2[0]. The worst case is when both loops are executed "as much as possibile", so when the state with i=n and j=n is reached (L1[n] = L2[n] or L1 and L2 have no elements in common).

What about complexity? We are talking about the worst case, so instructions belonging to the first loop are executed n times, while statements in the second loop are executed n*n = n2 times. All other statements are executed only once. So we have: n + n2 + 1. Your algorithm's time complexity is O(n2).

Hint: Sort algotithm perform O(nlogn), and then you can compare L1 and L2 in O(n).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 16 '17 at 19:49

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.