The total work done by an algorithm is the product of the runtime of a single iteration and the number of iterations performed. If I have an algorithm that takes t time for a single iteration and I run the algorithm 10 times, I do 10t work in total.

Suppose you are given a string's size in terms of n, where n is some number. You can figure out the runtime of a single iteration of your algorithm in terms of n. Then suppose you're given a target amount of work, also in terms of n, and told to figure out the number of iterations needed to meet that amount of work. A mathematically convenient way to do that would be put your number of iterations in terms of n, say n^b where b is some number, and then solve for b.

Q1. You are given a Text of length n⁸. How many times would you need to search the tree for a pattern of size n to do the same amount of work as building the tree?

Assume that the number of matches per search is much less than n.

Give your answer in terms of power of n. e.g. n⁹ would be 9.

Q2. You are given a Text of length n⁷ and x Patterns of size n. How big does x need to be in order for it to be as asymptotically efficient to use a suffix tree as it is to use the z-algorithm.

Assume that the number of matches per search is much less than n.

Give your answer in terms of power of n. e.g. n³ would be 3.