Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) := \sum_{x \leq y} f(x) \label{1}\tag{⋆} $$ for every $y \in \mathbb{F}_2^n$. Here, for $x=(x_1, \dots, x_n)$ and $y=(y_1, \dots, y_n)$ in $\mathbb{F}_2^n$, the notation $x \leq y$ means that $x_i \leq y_i$ for $i=1,\dots,n$.
I am interested in the space and time complexities of algorithms to compute the values $(\zeta_f(y))_{y \in \mathbb{F}_2^n}$ given $f$ as a black box.
The trivial algorithm that simply compute $\zeta_f(y)$ using \eqref{1} has time complexity $O(3^n)$$^{\text{[note 1]}}$ and space complexity $O(1)$.$^{\text{[note 2]}}$
The so-called Yate's algorithm has time complexity $O(n 2^n)$$^{\text{[note 3]}}$ and space complexity $O(2^n)$.
Is there an algorithm having smaller time complexity than the trivial algorithm and also smaller space complexity than the Yate's algorithm? Say $O(2.5^n)$ and $O(1.5^n)$, for example.
Thanks for any help.
Note 1: For each $y \in \mathbb{F}_2$ of Hamming weight $w$, to compute $\zeta_f(y)$ using \eqref{1} we have to sum $2^w$ values, so the time complexity is of the order $\sum_{w \leq n} 2^w \binom{n}{w} = 3^n$.
Note 2: Assuming that each value $\zeta_f(y)$ is printed immediately after its computation, and so it requires no memory to be stored.
Note 3: The time complexity cannot be less than $O(2^n)$, since there are $2^n$ values $(\zeta_f(y))_{y \in \mathbb{F}^n_2}$ to be computed.
