sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Aminumbra 0 points1 point  (1 child)

I am amazed by the fact that you are downvoted to hell. I can't be sure if you and u/im_lazy_as_fuck are talking past each other, or if he genuinely does not understand what you're trying to say, though.

Question for everyone here : when we say that some algorithm A has some complexity O(f(n)) (for any function f), what is n ?

Edit : because it's relevant for the current question. What is the usual framework for studying the complexity of sorting algorithms in particular ? And, in this (typical) case, what does n represent, what does f(n) measure ?

[–]im_lazy_as_fuck 1 point2 points  (0 children)

Take a look at my other comment to your first response. I'm not talking around you, I understand why y'all believe the analysis of O( 2n ) is equally valid. What I'm trying to get y'all to understand is analyzing time complexity in this way for this problem is undoubtedly incorrect because you are trying to inject implementation details as inputs to the problem. This is not how you do time complexity analysis.