Re: [cs2110-sp11] Complexity

4 views

Skip to first unread message

Message has been deleted

Nikos Karampatziakis

unread,

May 8, 2011, 9:07:54 PM5/8/11

to cornell-c...@googlegroups.com

contains() is O(n) for a list of size n.

On Sun, May 8, 2011 at 8:58 PM, Jisun Jung <jj...@cornell.edu> wrote:
> When we call contains method for some list of size n, should that count as
> O(n)? Or can we disregard it?

Robert Escriva

unread,

May 8, 2011, 9:16:56 PM5/8/11

to cornell-c...@googlegroups.com

I think the question was, "Can you assume that the complexity of O(n)
for a subroutine doesn't matter when trying to analyze the routine which
uses the subroutine." The answer is: Your running time analysis MUST
include the analysis of the subroutines you call. If you call the
contains method x times on a list of size n, then your running time is
O(xn).