what is the Big O for Returning List? aka return list (e.g. list=[1,2,...])

is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple types like list or arrays, etc.

  • 2
    $\begingroup$ How did you came up with your theory? I think if you have something like return list in C, you are actualliy returning a pointer to the head of the list list, which would be $\mathcal{O}(1)$. In other languages, you might implicitly make a copy of the whole list and return that, this would be $\mathcal{O}(n)$. Have you considered this for your question, yet? $\endgroup$ – ttnick Mar 18 '18 at 10:09
  • 2
    $\begingroup$ I don't know what you mean by "returning list", but the running time will depend on how the operation is implemented. And please note that there is no such thing as "The big-O notation for [some operation]". That's like asking for "The numerical notation of some person" -- what do you want to express as a number? Their height? Weight? Phone number? Something else? And, once you've decided what quantity you're representing with big-O, there's no such thing as "the big-O". Big-O gives upper bounds, so asking for "the big-O" of some function is like asking for "the number bigger than 10". $\endgroup$ – David Richerby Mar 18 '18 at 14:32
  • $\begingroup$ @DavidRicherby Looks like an answer to me. $\endgroup$ – Yuval Filmus Mar 30 '18 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.