How is Motoko's List.last function running in O(1)?

Samer · February 15, 2023, 7:49pm

It has to check every element starting at the head, so why not O(n)?

dfinity/motoko-base/blob/32efd710f1793aab87a0a84e26710b7bad4661fe/src/List.mo#L71


      
          ///
          /// Space: O(1)
          public func push<T>(x : T, l : List<T>) : List<T> = ?(x, l);
          
          
/// Return the last element of the list, if present.
          /// Example:
          /// ```motoko include=initialize
          /// List.last<Nat>(?(0, ?(1, null))) // => ?1
          /// ```
          ///
          /// Runtime: O(1)
          ///
          /// Space: O(1)
          public func last<T>(l : List<T>) : ?T {
            switch l {
              case null { null };
              case (?(x, null)) { ?x };
              case (?(_, t)) { last<T>(t) }
            }
          };

claudio · February 16, 2023, 1:25am

Sorry, that’s a typo. You are correct

Topic		Replies	Views
FIFO LinkedList Queue in Motoko Language Support	4	1006	June 8, 2020
Does Motoko support tail call optimization? Language Support Motoko	10	827	February 21, 2022
List bug report Developers	3	338	October 31, 2021
Doubly linked list in Motoko Language Support Motoko	14	1473	September 2, 2022
Why is the List.push() method not working in this example? Language Support	3	512	November 16, 2021

How is Motoko's List.last function running in O(1)?

Related topics