uppose that we have a function with a constant amount of work done in initialization, a call to a log-linearsorting algorithm, and a loop that iterates n times, doing a linear amount of work in each iteration. What is the running time of the algorithm

Question

Yurem Mora

Mathematics

27 November, 05:12

uppose that we have a function with a constant amount of work done in initialization, a call to a log-linearsorting algorithm, and a loop that iterates n times, doing a linear amount of work in each iteration. What is the running time of the algorithm

+2

Answers (1)

Know the Answer?

Chandler · Answer 1

The running time is quadratic (O (n²))

Step-by-step explanation:

For the set up, we have a constant running time of C. The, a log-linearsorting is called, thus, its execution time, denoted by T (n), is O (n*log (n)). Then, we call n times a linear iteration, with a running time of an+b, for certain constants a and b, thus, the running time of the algorithm is

C + T (n) + n * (a*n+b) = an²+bn + T + C

Since T (n) is O (n*log (n)) and n² is asymptotically bigger than n*log (n), then the running time of the algorith is quadratic, therefore, it is O (n²).