This is just a partial/general answer that addresses one of your doubts. I will let others address your question about the specific algorithms that you are mentioning.
Data efficiency refers to the number of samples or observations that you use during learning, as a function of the number of episodes, time steps or maybe time, to achieve a certain performance (e.g. return). I think that data efficiency is a synonym for sample efficiency, at least, in reinforcement learning. In RL, a sample could e.g. be a tuple $\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle$.
The time and space complexities of an algorithm indicate how much computation and memory the algorithm needs asymptotically. These are usually expressed as a function of the size of the input (which is measured in different ways, e.g. number of elements in a list or maybe the number of bits to represent a number), but this does not always have to be the case (e.g. you can also express the time complexity as a function of the output size, for a certain type of algorithm known as output-sensitive algorithm, or maybe as a function of the number of layers in a neural network). In your case, it's expressed as a function of $d$.
Now, let's say that we have 2 learning algorithms, $A$ and $B$, and that, on average, algorithm $A$ requires roughly $10^6$ samples to obtain the return $R$, while algorithm $B$ requires only $10^3$ samples to obtain the same return $R$. We can conclude that $B$ is more sample efficient than $A$. However, let's say that, at every time step, $B$ does an expensive calculation (e.g. it performs an algorithm that has exponential time complexity), while $A$ does a constant-time computation. We can say that $A$ has a better time complexity. Later, maybe we can come up with a new algorithm $C$, which has the same time complexity as $A$, but better sample efficiency, so we would probably use $C$ rather than $A$, but we could still choose $B$, provided that its time complexity is acceptable (e.g. exponential time would not be acceptable). So, you could also have an algorithm $D$ that is as sample efficient as $B$, but, at every step, it performs an update that requires exponential time, but it still requires the same number of time steps to get the same return $R$.
Note that time-steps in RL are not the same thing as time in time-complexity. Maybe this is where your confusion partially lies.
If the explanations above were confusing, then I think you should rigorously review the concepts of time/space complexity.
As a side note, computational learning theory is a branch of machine learning that studies learning algorithms from a theoretical/mathematical standpoint, i.e. the algorithms are analysed in terms of time complexity, space complexity and sample complexity, which is related to the sample efficiency, but not exactly the same thing.
