Let $G$ be a group given by multiplication table. We are also given an $a \in G$. To check that $a \in C(G)$, i.e. in the center of $G$.
One easiest way is for all elements $b \in G$ check whether $a.b = b.a$. But this requires $n-1$ many operations ( $a.b = b.a$ ). Is there any efficient ( less no of operations ) way to do this?
If you know a generating set $X$ for $G$, then it is sufficient to test whether $ax=xa$ for all $x \in X$. Since any finite group $G$ has a generating set of size at most $\log_2 |G|$, this potentially reduces the number of checks to $O(\log |G|)$.
But if you are not given a generating set, then it will take at least $O(|G|)$ operations to find one (IIRC that can be done in $O(|G| \log |G|)$) so this is no improvement on your simple method of checking everything. Although, as others have pointed out, you only need to check that $a$ commutes with $n/2+1$ elements.