Calculating entries of unitary transformation

Let $$U$$ be a unitary $$n$$-qubit transformation that applies a Hadamard on the $$k$$-th qubit and the identity on all the others. How would I go about calculating $$U_{ij}=\langle i | U | j \rangle$$ in polynomial time? Calculating all of $$U$$ is not feasible in polynomial time as it is a $$2^n \times 2^n$$ matrix.

If $$|i\rangle$$ and $$|j\rangle$$ are from computational basis, then we can write $$U = I \otimes I ~\otimes ... \otimes ~H ~\otimes ... \otimes ~ I \otimes I$$ $$\langle i | = \langle i_1| \otimes \langle i_2| ~\otimes ... \otimes ~\langle i_k| ~\otimes ... \otimes ~ \langle i_{n-1}| \otimes \langle i_n|$$ $$|j \rangle = |j_1\rangle \otimes |j_2\rangle ~\otimes ... \otimes ~ |j_k\rangle ~\otimes ... \otimes ~ | j_{n-1}\rangle \otimes | j_n\rangle$$ where every $$i_x$$ and $$j_x$$ are $$0$$ or $$1$$.
Then the product $$\langle i | U | j \rangle$$ will be $$\langle i | U | j \rangle = \langle i_1| j_1\rangle \otimes \langle i_2| j_2\rangle~\otimes ... \otimes ~\langle i_k|H|j_k\rangle ~\otimes ... \otimes ~ \langle i_{n-1}| j_{n-1}\rangle\otimes \langle i_n|j_n\rangle =$$ $$= \langle i_1| j_1\rangle \cdot \langle i_2| j_2\rangle~\cdot ... \cdot ~\langle i_k|H|j_k\rangle ~\cdot ... \cdot ~ \langle i_{n-1}| j_{n-1}\rangle\cdot \langle i_n|j_n\rangle$$ $$= \delta_{i_1j_1} \cdot \delta_{i_2j_2}~\cdot ... \cdot ~\langle i_k|H|j_k\rangle ~\cdot ... \cdot ~ \delta_{i_{n-1}j_{n-1}}\cdot \delta_{i_nj_n}$$ where $$\delta_{i_xj_x} = 1$$ if $$i_x = j_x$$ and $$0$$ otherwise.
If $$|i\rangle$$ and $$|j\rangle$$ are not from computational basis, then it's impossible to compute it that fast, because you need exponential number of parameters just to define $$|i\rangle$$ or $$|j\rangle$$.