NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself? Translated exercise:

Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses
  extra information $y$, which is is $\leq 3 \log n$ bits. What $f(n)$ can we
  say, that $R$ belongs to in ${\sf TIME}(f(n))$?


The only part I dont get is how a verifier using some (very small) extra memory would influence the problem $R$ beloging to a specific ${\sf TIME}(f(n))$ class.
Please just point me in the right direction. 
Any Wikipedia link or a single sentence. My book got nothing.
What does "extra information $y$, which is is $\leq 3 \log n$ bits" even mean?
 A: tl;dr: the keyword is enumeration. That is, you know that for any $x$, if there is a witness $y$ proving $x\in {\sf R}$ then it is small, so you can afford to try out all possible witnesses.
Stop reading here is you only wanted a clue.

Outline:
What it means is that the problem $R\in\sf NP$ satisfies the following. There exists an algorithm $M$ such that for any $x$ of size $\lvert x\rvert = n$:


*

*if $x\in R$, there there exists $y\in\{0,1\}^\ast$ with $\lvert y\rvert \leq 3\log_2 n$ such that $M(x,y)=1$;

*if $x\notin R$, there for any $y\in\{0,1\}^\ast$ (in particular with $\lvert y\rvert \leq 3\log_2 n$) we have $M(x,y)=0$.
Moreover, $M$ runs in time $O(n)$, when given inputs $x,y$ with $\lvert x\rvert = n$.
Now, why does the assumption that the certificate $y$ is small help? Well, here is the idea:

Given an input $x$ of size $n$, how much time does it take to try all possible $y\in\{0,1\}^\ast$ such that $\lvert y\rvert \leq 3\log_2 n$? 

More detail: (spoilers)
The answer is $O(n^3)$, since there are 
$$
\sum_{k=0}^{3\log_2 n} 2^k = \frac{2^{3\log_2 n+1}-1}{2-1} = 2^{3\log_2 n+1}-1 = \frac{n^3}{2}-1
$$
such "candidates" $y$.
So given $M$ as above, on input $x$ of size $n$ once can iterate over all possible witnesses $y$ of size at most $3\log_2 n$, and compute $M(x,y)$ for each of them. 


*

*If there exists $y^\ast$ such that $M(x,y^\ast)=1$, return $\sf accept$;

*If there is no $y$ such that $M(x,y)=1$, return $\sf reject$


and the loop overall takes time $O(n^3)\cdot O(n) = O(n^4)$ (checking $O(n^3)$ possibilities, with $O(n)$ computation for each.)
