1) Show the contents of the id array after each union operation when you use the

Question

1) Show the contents of the id array after each union operation when you use the quick union algorithm (Program I.I) to solve the connectivity problem for the sequence 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3. Also give the number of times the program accesses the id array for each input pair.

#include <iostream.h>

Static const int N = 10000;

int main ()

{int i, p, q, id[N];

for (i = 0; i < N; i++) id[i] = i;

while (cin >> p >> q)

{ int t = id[p];

if (t == id [q]) continue;

for (i = 0; i < N; i++)

if (id[i] == t) id[i] = id[q];

cout << " " << p << " " << q << endl;

}

}

2) For what value is N is 10N lg N>2N2?

3) Prove that O(1) is the same as O(2)

4) You are given the information that the time complexity of one problem is N log N and that the time complexity of another problem is N3.What does this statement imply about the relative performance of specific algorithms that solve the problems?

Explanation / Answer

answer 2

10N*logN > 2N^2

2N(5*logN-N) > 0

N>0 or 5logN - N >0

5logN>N

logN > N/5

N > e^(N/5)

If it is not log and if it is ln with base 10 then

10N*ln N > 2N^2

2N(5*ln N-N) > 0

N>0 or 5ln N - N >0

5ln N>N

ln N > N/5

N > 10^(N/5)

answer 3

(T_1 = 1 & T_2 = 2)   

   (T_1 = 1 <= T_2=2 for all n)   

   ( herefore O(1) is same as O(2))

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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