Question

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

Answer 1

Answer:

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²).