Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Edit Distance Problem”.

1. Which of the following methods can be used to solve the edit distance problem?
a) Recursion
b) Dynamic programming
c) Both dynamic programming and recursion
d) Greedy Algorithm
Answer: c
Clarification: Both dynamic programming and recursion can be used to solve the edit distance problem.

2. The edit distance satisfies the axioms of a metric when the costs are non-negative.
a) True
b) False

Answer: a
Clarification: d(s,s) = 0, since each string can be transformed into itself without any change.
d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
d(s1, s2) = d(s2, s1)
d(s1, s3) <= d(s1, s2) + d(s2, s3)
Thus, the edit distance satisfies the axioms of a metric.

3. Which of the following is an application of the edit distance problem?
a) Approximate string matching
b) Spelling correction
c) Similarity of DNA
d) Approximate string matching, Spelling Correction and Similarity of DNA

Answer: d
Clarification: All of the mentioned are the applications of the edit distance problem.

4. In which of the following cases will the edit distance between two strings be zero?
a) When one string is a substring of another
b) When the lengths of the two strings are equal
c) When the two strings are equal
d) The edit distance can never be zero
Answer: c
Clarification: The edit distance will be zero only when the two strings are equal.

5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
a) True
b) False
View Answer

Answer: a
Clarification: Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.

6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
a) 3
b) 4
c) 5
d) 6

Answer: b
Clarification: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.

7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
a) 0
b) 4
c) 2
d) 3

Answer: b
Clarification: The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.

8. Consider the following dynamic programming implementation of the edit distance problem:

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                _____________;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[i-1][j] = min
b) arr[i][j-1] = min
c) arr[i-1][j-1] = min
d) arr[i][j] = min

Answer: d
Clarification: The line arr[i][j] = min completes the above code.

9. What is the time complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)

Answer: c
Clarification: The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

10. What is the space complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

11. What is the output of the following code?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
      arr[i][0] = i;
     for(i = 0; i <= len2; i++)
      arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                      min = arr[i-1][j-1];
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                     min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
Answer: d
Clarification: The program prints the edit distance between the strings “abcd” and “defg”, which is 4.

12. What is the value stored in arr[2][2] when the following code is executed?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
      int len1,len2,i,j,min;
      len1 = strlen(s1);
      len2 = strlen(s2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0;i <= len1; i++)
        arr[i][0] = i;
      for(i = 0; i <= len2; i++)
         arr[0][i] = i;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                 min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
                 if(s1[i - 1] == s2[j - 1])
                 {
                      if(arr[i-1][j-1] < min)
                        min = arr[i-1][j-1];
                 }
                 else
                 {
                      if(arr[i-1][j-1] + 1 < min)
                        min = arr[i-1][j-1] + 1;
                 }
                 arr[i][j] = min;
           }
      }
      return arr[len1][len2];
}
int main()
{
      char s1[] = "abcd", s2[] = "defg";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The value stored in arr[2][2] when the above code is executed is 2.

13. What is the output of the following code?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                     min = arr[i-1][j-1];
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                     min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "pqrstuv", s2[] = "prstuv";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
View Answer

Answer: a
Clarification: The code prints the edit distance between the two strings, which is 1.

Data Structures & Algorithms Multiple Choice Questions on “Beaufort Cipher”.

1. Beaufort cipher is an example of ____________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: b
Clarification: Beaufort cipher is a substitution cipher. It falls under the category of poly alphabetic cipher as it uses multiple substitutions at different positions in order to cipher the plain text.

2. Encryption in beaufort cipher is done using ____________
a) trithemius table
b) vigenere cycle
c) tabula recta
d) four square table

Answer: c
Clarification: Encryption of plain text in beaufort cipher is done by making use of tabula recta. The same table is also used for encryption in vigenere cipher and running key cipher.

3. Which of the following is reciprocal cipher?
a) vigenere cipher
b) autokey cipher
c) running key cipher
d) beaufort cipher

Answer: d
Clarification: A reciprocal cipher is a cipher in which if we try to encrypt the cipher text (using the same cipher) then we gets the plain text as a result. In other words, the process of decryption and encryption is exactly the same.

4. Which of the following is a difference between beaufort cipher and vigenere cipher?
a) they use different tables for encryption
b) vigenere cipher is poly alphabetic whereas beaufort cipher is mono alphabetic
c) vigenere cipher uses a key whereas no key is required for using beaufort cipher
d) they use the same table for encryption, but in a different manner
Answer: d
Clarification: Beaufort cipher is a variation of vigenere cipher. They use the same table i.e. tabula recta for encryption but the table is used in a different manner.

5. Beaufort cipher is a variant of ____________
a) autokey cipher
b) vigenere cipher
c) hill cipher
d) route cipher
Answer: b
Clarification: Beaufort cipher is a variant of vigenere cipher. The difference is that beaufort cipher uses tabula recta in a different manner for encryption.

6. The process of decryption is exactly same as that of encryption in beaufort cipher.
a) True
b) False

Answer: a
Clarification: Beaufort cipher is an example of reciprocal cipher. So that is why the process of decryption is exactly same as that of encryption in beaufort cipher.

7. What will be the plain text corresponding to cipher text “SEDGKG” if beaufort cipher is used with key as “KEY”?
a) PRISON
b) DEATHS
c) SAVEUS
d) ABUSED
Answer: c
Clarification: The process of decryption and encryption are exactly the same in beaufort cipher. So the corresponding plain text would be “SAVEUS”.

8. Beaufort cipher and variant beaufort cipher are same ciphers.
a) True
b) False

Answer: b
Clarification: Beaufort cipher is different from variant beaufort cipher. Variant beaufort cipher is a variant of beaufort cipher.

9. What will be the ciphered text corresponding to “” if beaufort cipher is used for encryption with key as “KEY”?
a) SBPISZTKZH
b) TCQJTAULAI
c) SELFQEXBHM
d) SPBISZKTZH

Answer: c
Clarification: For encrypting plain text choose the first letter of plain text (i.e. S) in the first horizontal row. Then find the first letter of key (i.e. K) in the column obtained in the first step. Finally, choose the leftmost letter of the row (i.e. S) obtained in the previous step. So the corresponding cipher text is “SELFQEXBHM”.

10. What will be the ciphered text corresponding to “ALGORITHM” if beaufort cipher is used for encryption with key as “KEY”?
a) BNJSWOAPV
b) KTSWNQRXM
c) AMIRVNZOU
d) MBPHJSNIU

Answer: b
Clarification: For encrypting plain text choose the first letter of plain text (i.e. A) in the first horizontal row. Then find the first letter of key (i.e. K) in the column obtained in the first step. Finally, choose the leftmost letter of the row (i.e. K) obtained in the previous step. So the corresponding cipher text is “KTSWNQRXM”.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Hamiltonian Path Problem”.

1. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
a) branch and bound
b) iterative improvement
c) divide and conquer
d) greedy algorithm
Answer: a
Clarification: The Hamiltonian path problem can be solved efficiently using branch and bound approach. It can also be solved using a backtracking approach.

2. The problem of finding a path in a graph that visits every vertex exactly once is called?
a) Hamiltonian path problem
b) Hamiltonian cycle problem
c) Subset sum problem
d) Turnpike reconstruction problem

Answer: a
Clarification: Hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas Hamiltonian cycle problem is finding a cycle in a graph.

3. Hamiltonian path problem is _________
a) NP problem
b) N class problem
c) P class problem
d) NP complete problem

Answer: d
Clarification: Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an NP- complete problem.

4. There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
a) true
b) false

Answer: b
Clarification: There is a relationship between Hamiltonian path problem and Hamiltonian circuit problem. The Hamiltonian path in graph G is equal to Hamiltonian cycle in graph H under certain conditions.

5. Which of the following problems is similar to that of a Hamiltonian path problem?
a) knapsack problem
b) closest pair problem
c) travelling salesman problem
d) assignment problem

Answer: c
Clarification: Hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.

6. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
a) Martello
b) Monte Carlo
c) Leonard
d) Bellman

Answer: a
Clarification: The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.

7. In what time can the Hamiltonian path problem can be solved using dynamic programming?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(N² 2^N)

Answer: d
Clarification: Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N² 2^N).

8. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
a) true
b) false

Answer: a
Clarification: According to a handshaking lemma, in graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.

9. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
a) Karp
b) Leonard Adleman
c) Andreas Bjorklund
d) Martello
Answer: c
Clarification: Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of Hamiltonian cycles.

10. For a graph of degree three, in what time can a Hamiltonian path be found?
a) O(0.251ⁿ)
b) O(0.401ⁿ)
c) O(0.167ⁿ)
d) O(0.151ⁿ)
Answer: a
Clarification: For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251ⁿ).

11. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
a) O(N!)
b) O(N! * N)
c) O(log N)
d) O(N)
Answer: b
Clarification: For a graph having N vertices traverse the permutations in N! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).

12. How many Hamiltonian paths does the following graph have?

a) 1
b) 2
c) 3
d) 4

Answer: a
Clarification: The above graph has only one Hamiltonian path that is from a-b-c-d-e.

13. How many Hamiltonian paths does the following graph have?

a) 1
b) 2
c) 0
d) 3

Answer: c
Clarification: The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.

& Algorithms.

Data Structures & Algorithms Multiple Choice Questions on “Linear Search Recursive”.

1. Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?
a) Both execute at same speed
b) Linear search(recursive) is faster
c) Linear search(Iterative) is faster
d) Cant be said

Answer: c
Clarification: The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.

2. Is the space consumed by the linear search(recursive) and linear search(iterative) same?
a) No, recursive algorithm consumes more space
b) No, recursive algorithm consumes less space
c) Yes
d) Nothing can be said

Answer: a
Clarification: The recursive algorithm consumes more space as it involves the usage the stack space(calls the function numerous times).

3. What is the worst case runtime of linear search(recursive) algorithm?
a) O(n)
b) O(logn)
c) O(n²)
d) O(nx)

Answer: a
Clarification: In the worst case scenario, there might be a need of calling the stack n times. Therfore O(n).

4. Linear search(recursive) algorithm used in _____________
a) When the size of the dataset is low
b) When the size of the dataset is large
c) When the dataset is unordered
d) Never used

Answer: a
Clarification: It is used when the size of the dataset is low as its runtime is O(n) which is more when compared to the binary search O(logn).

5. The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found? (By using linear search(recursive) algorithm)
a) 4th call
b) 3rd call
c) 6th call
d) 5th call

Answer: a
Clarification: Provided that the search starts from the first element, the function calls itself till the element is found. In this case, the element is found in 4th call.

6. The array is as follows: 1,2,3,6,8,10. Given that the number 17 is to be searched. At which call it tells that there’s no such element? (By using linear search(recursive) algorithm)
a) 7th call
b) 9th call
c) 17th call
d) The function calls itself infinite number of times

Answer: a
Clarification: The function calls itself till the element is found. But at the 7th call it terminates as goes outside the array.

7. What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?
a) O(1)
b) O(n)
c) O(logn)
d) O(nx)

Answer: a
Clarification: The best case occurs when the given element to be found is at the first position. Therefore O(1) is the correct answer.

8. Which of the following code snippet performs linear search recursively?
a)

        for(i=0;i<n;i++)
	{
		if(a[i]==key)
		printf("element found");
	}

b)

        LinearSearch(int[] a, n,key)
	{
		if(n<1)
		return False
		if(a[n]==key)
		return True
		else
		LinearSearch(a,n-1,key)
	}

c)

        LinearSearch(int[] a, n,key)
	{
		if(n<1)
		return True
		if(a[n]==key)
		return False
		else
		LinearSearch(a,n-1,key)
	}

d)

        LinearSearch(int[] a, n,key)
	{
		if(n<1)
		return False
		if(a[n]==key)
		return True
		else
		LinearSearch(a,n+1,key)
	}

Answer: b
Clarification: Compare n with first element in arr[]. If element is found at first position, return it. Else recur for remaining array and n.

9. Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?
a) Binary search can’t be used
b) Linear search can’t be used
c) Both cannot be used
d) Both can be used
Answer: a
Clarification: As binary search requires comparison, it is required that the list be ordered. Whereas this doesn’t matter for linear search.

10. What is the recurrence relation for the linear search recursive algorithm?
a) T(n-2)+c
b) 2T(n-1)+c
c) T(n-1)+c
d) T(n+1)+c
Answer: c
Clarification: After each call in the recursive algorithm, the size of n is reduced by 1. Therefore the optimal solution is T(n-1)+c.

Data Structures & Algorithms Multiple Choice Questions on “Comb Sort”.

1. Comb sort is an improved version of _______
a) Selection sort
b) Bubble sort
c) Insertion sort
d) Merge sort

Answer: b
Clarification: Comb sort compares two elements at a variable gap from each other in each iteration unlike bubble sort where the gap remains 1. This reduces the average time complexity of comb sort.

2. The gap between two elements being compared shrinks by a factor of _______ after every iteration.
a) 1.1
b) 1.2
c) 1.3
d) 1.4

Answer: c
Clarification: It has been found experimentally that the gap between the two elements should shrink by a factor of 1.3 after each iteration for the most efficient sorting.

3. The initial gap between two elements being compared _______
a) is equal to number of elements in the array
b) is equal to 1.3
c) depends on the number of iterations
d) depends on the compiler being used

Answer: a
Clarification: Initial gap is taken to be equal to the number of elements in the array and shrinks by a factor of 1.3 in each iteration, initial gap is independent of the number of iterations and compiler being used.

4. What is the worst case time complexity of comb sort?
a) O(n²)
b) O(n log n)
c) O(n)
d) O(n²/2^a) (a=number of increment)

Answer: a
Clarification: Worst case complexity is observed when the input array is reverse sorted. This is same as the worst case complexity of bubble sort.

5. The gap value after 3 iterations in an array with 6 elements will be _______
a) 4
b) 3
c) 2
d) 1

Answer: c
Clarification: Initially the gap value will be 6. For the first iteration, it will be 6/1.3=4 then 4/1.3=3 for second iteration and 3/1.3=2 for the third iteration.

6. Auxiliary space used by comb sort is _______
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Auxiliary space used by comb sort is O(1) as it does not use any extra space for manipulating the input.

7. The given array is arr={7,4,5,8,1,2}. The number of iterations required to sort the array using comb sort and bubble sort respectively will be _______
a) 7 and 8
b) 5 and 6
c) 5 and 5
d) 4 and 5

Answer: d
Clarification: Comb sort takes 1 iteration less as compared to bubble sort as it makes use of variable gap value whereas bubble sort uses a constant gap value of 1.

8. Comb sort is a stable sorting algorithm.
a) True
b) False
Answer: b
Clarification: Comb sort is not a stable sorting algorithm as it does not sort the repeated elements in the same order as they appear in the input.

9. What is the best case time complexity of comb sort and bubble sort respectively?
a) O(n²) and O(n log n)
b) O(n log n) and O(n)
c) O(n) and O(n²)
d) O(n²/2^a) (a=number of increment) and O(n²)

Answer: b
Clarification: Best case complexity for comb sort and bubble sort is O(n log n) and O(n) respectively. It occurs when the input array is already sorted.

10. What is the advantage of comb sort over merge sort?
a) Comb sort is an in place sorting algorithm
b) Comb sort is a stable sorting algorithm
c) Comb sort is more efficient
d) It has no advantage
Answer: a
Clarification: Comb sort does not require auxiliary space for manipulating input so it is an in place sorting algorithm but merge sort does require O(n) of auxiliary space which makes comb sort better in terms of space complexity.