(Solved): a. Determine the worst-case running time of the following algorithm: b.Calculate the running time ...

a. Determine the worst-case running time of the following algorithm:

b.Calculate the running time of an algorithm using the master theorem, described by the following recurrence relation:

c.Solve the following using the substitution method:

ALGORITHM \( (\mathrm{x}, \mathrm{n}): \) \( \quad \) if \( (\mathrm{n}==0): \) return \( \mathrm{z}=0 \) for \( (1 \) to \( \mathrm{n}): \mathrm{z}=\mathrm{z}+\mathrm{n} \) if \( \mathrm{n} \div 2==0 \) : \[ \mathrm{y}=\mathrm{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2) * \operatorname{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2) \] else : \( \mathrm{y}=\mathrm{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2) * \operatorname{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2) \) * \( \mathrm{z} \) return \( \mathrm{y}+(\mathrm{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2) * \operatorname{ALGORITHM}(\mathrm{x}, \mathrm{n} / 2)) \) \( 243 T\left(\frac{n}{3}\right)+n^{2} \operatorname{lgn} \) \( T(n)=T\left(\frac{2 n}{5}\right)+T\left(\frac{3 n}{5}\right)+O(n \operatorname{lgn}) \)