3. Consider two arrays of characters A and B, where n is the size of the largest
ID: 3932817 • Letter: 3
Question
3. Consider two arrays of characters A and B, where n is the size of the largest array. You have to design a method that returns a “true” or a false” depending on whether one of the elements is a permutation of another. For example, if A = a,n,d,t,g and B = d,t,a,g,n or a,n,d,t,g , then the answer will be “true” but when A = a,n,d,t,g and B = d,t,c,g or t,a,m,d.g then the answer sill be “false”. (a) Propose an O(n2) algorithm to solve this problem. (b) Propose another algorithm for the same problem with running time better than O(n2) . Outline your idea in pseudo-code or in plain English (3-4 sentences only)
Explanation / Answer
a.Algoritm 1:
step1: char[] a={'a','a','d','t','g'};
char[] b={'d','a','t','g','a'};
step2: if(a.length==b.length)
N =a.length
goto step3;
else
return false;
goto step4;
step3:
for i is 0 to N // This loop takes n iterations
flag=0;
for j=0 to N // this inner loop takes n iterations => N2 iterations
{
if(a[i]==b[j]&&flag==0)
{
flag=1;
}
}
if(flag==0)
{
return false;
}
}
retrun true;
}
step4:
End;
Time complescity: O(n2) algorithm to solve this problem for BEST, AVARAGE and WORST case also
b. Algoritm 2:
step1: char[] a={'a','a','d','t','g'};
char[] b={'d','a','t','g','a'};
step2: if(a.length==b.length)
N =a.length
goto step3;
else
return false;
goto step4;
step3:
for i is 0 to N // This loop takes n iterations
flag=0;
for j=0 to N // this inner loop takes n iterations => N2 iterations
{
if(a[i]==b[j])
{
flag=1;
break from inner FOR loop
}
}
if(flag==0)
{
return false;
}
}
retrun true;
}
step4:
End;
Time complescity: T is less then O(n2) algorithm to solve this problem for BEST, AVARAGE and WORST case also.
Example:
a={'a','n','d','t','g'};
b={'d','a','t','g','n'};
This Legnth n=5
The two loops takes time to excute (n2) =>5 * 5 =25 if it find elements
Example:
a={'a','n','d','t','g'};
b={'d','a','t','g','n'};
This Legnth n=5
The two loops takes time to excute (n2) but it takes less then the Algorithm 1.
->'a' finds in= 2 iterations
->' n' finds in =5 iterations
->' d' finds in =1 iterations
->' t' finds in =2 iterations
->' g' finds in =4 iterations
Total time=15 iterations only
Algorithm 1 Algorithm 1Example:
a={'a','n','d','t','g'};
b={'d','a','t','g','n'};
This Legnth n=5
The two loops takes time to excute (n2) =>5 * 5 =25 if it find elements
Example:
a={'a','n','d','t','g'};
b={'d','a','t','g','n'};
This Legnth n=5
The two loops takes time to excute (n2) but it takes less then the Algorithm 1.
->'a' finds in= 2 iterations
->' n' finds in =5 iterations
->' d' finds in =1 iterations
->' t' finds in =2 iterations
->' g' finds in =4 iterations
Total time=15 iterations only
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.