Приветствую.

Сразу скажу, что формальными методиками определения временной сложности алгоритма не владею, но в "обычном" коде обычно могу определить на глазок. Но не в случае бесконечных потоков. Вот, по мотивам упражнений из SICP (не помню, какой номер), поток чисел, простыми делителями которых являются только 2, 3, 5:

(* вспомогательные функции *)
(* для простоты считаем, что потоки бесконечные  *)
let rec merge_streams s1 s2 =
    let h1 = Stream.next s1 and
        h2 = Stream.next s2 in
        if h1<h2 then
            (* Вызов Stream.next деструктивен,
               не забываем положить h1 или h2 на место *)
            [< 'h1;  merge_streams s1 [<'h2;s2>] >]
        else if h2<h1 then
            [< 'h2; merge_streams [<'h1;s1>] s2 >]
        else
            [< 'h1; merge_streams s1 s2>];;
let stream_map f =
    let rec impl s = [< '(f (Stream.next s)); impl s  >]
    in impl;;
let scale_stream k = stream_map (fun x -> k*x);;

(* собственно, поток *)
let rec s235 () =
    (merge_streams
         [< '5; scale_stream 5 (s235()) >]
         (merge_streams
              [< '3; scale_stream 3 (s235()) >]
              [< '2; scale_stream 2 (s235()) >]));;

Замеры времени на выполнение Stream.npeek n s235() дают если не экспоненту, то довольно круто растущий полином от n. Попытки представить процесс вычисления данного потока по шагам исчерпали всю мою виртуальную память. Просветите?