Question

5 Comparing Substrings Here you'll evaluate running times of algorithms whose input size is expressed using two parameters. Let T[l.n] and T'[1.n] be strings of length n, over a finite alphabet (For example, T and T' might be over the alphabet {A, C, G, T), and represent DNA strands.) A function Match indicates whether or not a letter of T matches a letter of T. That is, for 1 i,j Sn, Match(i,j) = 1, =0, if7h otherwise. =T'Li] Fix k,1 S k Sn. For 1 S i,j s n-k+1, the score of any two length-k substrings Tii + k-1] and T'Lİ.j + k-1] of T and T' respectively is given by k-1 Σ Match(i + l, j + 1). Algorithm Compute-Scores below computes all scores and stores them in a two-dimensional array called Score. Assume that calls to function Match take Θ (1) time and that array Score has already been created. Algorithm Compute-Scores (T[1.n), T [I.n],k) // T and T are length-n strings and 1 S kSn For i from 1 to n-k + 1 For j from 1 to n - k+1 // compute score of Tli..i+ k-1] and T'Uj +k-1] and store in Scoreli, j] Scoreli,jl - E Match(i+L,j +l)

  

1st photo is the introduction. 2nd photo are the questions. Thanks in advance!

Answer 1

Ans .1 -> is the time complexity of given algorithm .

Theta ((n - k)^2 k) is the time complexity of given algorithm. Theoretical proof- > Match() function is used in summation with range (0) to (k - 1) so the time complexity is k there are two loops Outer loop and inner loop Outer loop is having range i = 1 to i = (n - k + 1) so total time complexity of this loop is (n - k) Inner loop is having range j = 1 to j = (n - k + 1) so total time complexity of this loop is (n - k) for every (Outer loop)i , (inner loop) j runs n-k times. And for every j Match() function is called k times So for (n - k) times of i , j will run (n - k) times (n - k) times and for (n-k)*(n-k) j , match function will be called (n - k) times (n - k) times k times We know this algorithm

Theoratical proof-> Match() function is used in summation with range (0) to (k-1) so the time complexity is k

there are two loops Outer loop and inner loop

Outer loop is having range i=1 to i = (n-k+1) so total time complexity of this loop is (n-k)

Inner loop is having range j=1 to j = (n-k+1) so total time complexity of this loop is (n-k)

for every (Outer loop )i , (inner loop) j runs n-k times. And for every j Match() function is called k times

So for (n-k) times of i , j will run (n-k)*(n-k) times and for (n-k)*(n-k) j , match function will be called (n-k)*(n-k)*k times

Ans 2 ->We know this algorithm is simply computing the total matching in substring of size k

Here Score[i,j] contains matching no of elements in substring of length k starts with index i in first string and starts with index j in second string

Compute-Scores

This algorithm is using only 2 loops without any summation

First we are computing in score array total score till I,j the we are subtracting previous results before substring of length k

Its Time complexity is

Ans 3-> Its worst case Time complexity is

Thanks for Question

If you have any doubts Feel free to ask your queries.