I need the full answer please For 3 & 4. Please don’t copy from the internet Tak

Question

I need the full answer please
For 3 & 4.
Please don’t copy from the internet

Take your time

Thank you.

3. The number of operations executed by algorithms A and B is 8n logn and 2, respec- tively. Determine no such that A is better than B for n2 o. 4. Algorithm analysis: Give a big-Oh characterization, in terms of n, of the running time of the method below. Explain. l/ Returns true if there is no element common to all three arays 2public static boolean dinjoint2(int groupA int groupB, int 1 groupC) for (int a:goupA) 4for (int b : groupB) if (ab) //only check C when find match bon. A and B // and thus b-cas we for (int c: groupC) return fahe / we found a common value //we reach ths, sets are diyott 10 Code Fragment 4c Algorithm disjoint2 for testing three-way se dijointmess

Explanation / Answer

3)Given no. of operations executed by algorithm A: 8nlog(n)

and no. of operations executed by B: 2n2

so to A to be better algorithm than B, the time complexity(or say the no. of operations executed) of A should be less than that of B,

i.e. 8n*log(n) < 2n2

we have to find the number(n0) above which the above inequality holds.

8n*log(n)=n2

4n*log(n)=n2

n2 - 4n*log(n)=0

n(n-4log(n))=0

n=0 or n-4log(n)=0

n=4log(n)

n=16 i.e.n0

therefore for all n>=16 A is the better algorithm in comparison to B

4.) Let all the three groups(or arrays) contains n elements,

First if condition checks, if a ( element of groupA) is equal to b (element of groupB) if yes then only the third for loop (of c) executes, so worst-case scenerio occurs when all the elements in groupA and groupB is same

i.e goupA: aaaaaaa....

i.e goupB: aaaaaaa....

in this case all the three loops will execute n times each and the time complexity (i.e. worst-case) wil be big-oh of n3

or O(n3).

//If you have any doubt regarding the answer please ask in the comment section (before voting (: )

//please upvote

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.