Question

How would you explain asymptotic complexity in simple terms? For example, if you were to explain to a non-technical person that an algorithm runs in O(nlog n) time in the worst-case scenario, how would you describe it?

Answer 1

the graph of Onlogn is smwhat linear

Answer 2

what is this question exactly about?

Answer 3

@hartnn can you tell anything about this?

Answer 4

A linearithmic function (portmanteau of linear and logarithmic) is a function of the form n · log n (i.e., a product of a linear and a logarithmic term). An algorithm is said to run in linearithmic time if T(n) = O(n log n). Compared to other functions, a linearithmic function is ω(n), o(n1+ε) for every ε > 0, and Θ(n · log n). Thus, a linearithmic term grows faster than a linear term but slower than any polynomial in n with exponent strictly greater than 1.
An algorithm is said to run in quasilinear time if T(n) = O(n logk n) for any constant k. Quasilinear time algorithms are also o(n1+ε) for every ε > 0, and thus run faster than any polynomial in n with exponent strictly greater than 1.
In many cases, the n · log n running time is simply the result of performing a Θ(log n) operation n times. For example, binary tree sort creates a binary tree by inserting each element of the n-sized array one by one. Since the insert operation on a self-balancing binary search tree takes O(log n) time, the entire algorithm takes linearithmic time.
Comparison sorts require at least linearithmic number of comparisons in the worst case because log(n!) = Θ(n log n), by Stirling's approximation. They also frequently arise from the recurrence relation T(n) = 2 T(n/2) + O(n).
does this make any sense :D

Answer 5

The thing is, I know what asymptotic complexity is, but if I were to explain to a manager that say, heapsort, runs in O(n log n), how would I explain it to him, in layman terms?

Answer 6

And in just a few sentences, if possible (1 sentence is best).

Answer 7

i can add a statement :
more the nested loops in the program, more is the time complexity.
like if there is a loop inside a loop, then time complexity = O(n^2)
if there is a loop, inside a loop inside a loop, then O(n^3)
and if only one loop, no nesting, O(n)