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
Doubly linked list in Motoko Language Support Motoko	14	1169	September 2, 2022
FIFO LinkedList Queue in Motoko Language Support	4	935	June 8, 2020
Help me understand the Motoko documentation Developers	3	785	March 10, 2022
New Let Binding and Serialization Improvements: Motoko Updates Language Support Motoko	13	1225	April 3, 2023
Recursion in Motoko Motoko	1	210	December 15, 2023

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

Related Topics