Chan, I think you're confused because you expect that the function will visit each element of the lists (if they are the same size). Compiler short circuits && operator so your loop runs only til the first element that differs. If you swap the arguments to && you should get the behavior of visiting all elements (which is of course undesirable in practice) On Feb 22, 2016 15:02, "Anton Bachin" wrote: > But the complexity of this function is not constant if you fix only the > list length. It still varies quadratically in the location of the first > pair of elements that are different, because the “outer iteration” is > performed that many times, and the “inner" List.lengths visit at least that > many elements each time, since this location (if it exists) is less than > the list length. Hence, the behavior you are observing. > > > On Feb 22, 2016, at 13:57, Chan Ngo wrote: > > > > Hi Johannes and Anton, > > > > thanks for the information, but I did not mean the time complexity of > the function is constant (Big O notation). I mean the amount of time of > execution is constant when we fix the list length. > > > > In fact, I want to write a function that the running time is constant > (not the time complexity) given the size of input is fixed. That means it > does not depend on the characteristic of the input. > > > > Best, > > Chan > > > >> On Feb 22, 2016, at 2:51 PM, Anton Bachin > wrote: > >> > >> 1. You are computing the length of l1 and l2 every iteration. On the > first iteration, it is the lengths of the original lists. On the second > iteration, it is the lengths of their tails. This function takes time > quadratic in the maximum of (length l1, length l2), as written. List.length > itself takes linear time. > >> > >> 2. If h1 and h2 are nontrivial types, structural equality may take a > nontrivial amount of time to compute. > >> > >>> On Feb 22, 2016, at 13:45, Chan Ngo wrote: > >>> > >>> Dear all, > >>> > >>> I have write a simple function to compare two lists as below: > >>> > >>> let rec lcomp l1 l2 = > >>> if (List.length l1 != List.length l2) > >>> then false > >>> else match l1, l2 with > >>> | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2 > >>> | _, _ -> true;; > >>> > >>> In theory, we can see that the execution is a function of length of l1 > and l2 (in case they are same length, otherwise it return immediately) and > it is constant time (i.e., we fixed the length of l1 and l2). However, in > fact, when I run this function with two lists of around 100 elements, > >>> + with only 10th element is different: it takes 0.000027s > >>> + with only 90th element is different: it takes 0.000116s > >>> > >>> You see the execution times are really different. Thus, I wonder that > the compiler did some optimization? Does anyone have some pointers? > >>> > >>> Thanks, > >>> Chan > >>> > >>> > >>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes < > simon.cruanes.2007@m4x.org> wrote: > >>>> > >>>> Hello, > >>>> > >>>> I released bigstring.0.1 yesterday, a small module for dealing with > >>>> bigarrays of chars. It used to be part of containers, but is useful on > >>>> its own for low level IO, mirage, etc.; hence the split. The license > is > >>>> BSD-2-clauses. > >>>> > >>>> Code, issues, etc. can be found at > https://github.com/c-cube/ocaml-bigstring , > >>>> and contributions and criticism are welcome. > >>>> > >>>> Cheers, > >>>> > >>>> -- > >>>> Simon Cruanes > >>>> > >>>> http://weusepgp.info/ > >>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 > 49AA 62B6 > >>> > >>> > >>> -- > >>> Caml-list mailing list. Subscription management and archives: > >>> https://sympa.inria.fr/sympa/arc/caml-list > >>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > >>> Bug reports: http://caml.inria.fr/bin/caml-bugs > >> > > > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs