3 Consider two arrays of characters A and B where n is the s

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)

Solution

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 => N^{2 iterations}
{
if(a[i]==b[j]&&flag==0)
{   
flag=1;
}
  
}
if(flag==0)
{
   return false;
}
}
retrun true;
}
step4:
End;

Time complescity: O(n²) 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 => N^{2 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(n²) 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 (n²) =>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 (n²) 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