Please show steps-by-steps detail. Please state which method you used.

(a) What is the bruteforce runtime for creating a BWT? (b)Show that BWT[ITISAi] 1], where T is the input string BWT[I is the character at position i in the BWT string for T, and SA[I is the i'th entry in the suffix array for T Note this shows how to compute the BWT from the SA. What about the other direction? If we have the BWT, what else would we need to compute the SA, and in linear time