Need help solving the following problem, If anything can be used from the proofs from the Understanding Machine Learning: From Theory to Algorithms by Shai & Shai it may be used, just please reference it

A decision list may be thought of as an ordered sequence of if$-$then$-$else statements. The sequence of conditions in the decision list is tested in order, and the answer associated with the first satisfied condition is output.

More formally, a $k-$decision list over the boolean variables $x_1,x_2,$dots,$x_n$ is an ordered sequence $L=\{(c_1,b_1),(c_2,b_2),$dots,$(c_l,b_l)\}$ and a bit $b,$ in which each $c_i$ is a conjunction of at most $k$ literals over $x_1,x_2,$dots,$x_n$ and each $b_{i}in\{0,1\}.$ For any input ain$\{0,1{\}}^n,$ the value $L(a)$ is defined to be $b_j$ where $j$ is the smallest index satisfying $c_j(a)=1$; if no such index exists, then $L(a)=b.$ Thus, $b$ is the "default" value in case a falls off the end of the list. We call $b_i$ the bit associated with the condition $c_i.$

The next figure shows an example of a $2-$decision list along with its evaluation on a particular input.

Figure $1$: A $2-$decision list and the path followed by an input. Evaluation starts at the leftmost item and continues to the right until the first condition is satisfied, at which point the binary value below becomes the final result of the evaluation.

Show that the VC dimension of $1-$decision lists over $\{0,1{\}}^n$ is lower and upper bounded by linear functions, by showing that there exists $,,,inR$ such that:

$*n+$VCdim$(H_{1-\text{d}\text{e}\text{c}\text{i}\text{s}\text{i}\text{o}\text{n}\text{l}\text{i}\text{s}\text{t}})*n+$

Hint: Show that $1-$decision lists over $\{0,1{\}}^n$ compute linearly separable functions $($halfspaces$)$