Number of operations for Elgamal cryptosystem In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says 


  "Roughly speaking, in order to achieve $k$ bits of security,
  encryption and decryption for Elgamal, RSA, and ECC, requires
  $\mathcal{O}(k^3)$ operations, while encryption and decryption for
  lattice-based systems requires only $\mathcal{O}(k^2)$ operations".


Why does Elgamal encryption and decryption require $\mathcal{O}(k^3)$ operations?
Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems require only $\mathcal{O}(k^2)$ operations.

That quote uses &quot;$k$ bits of security&quot; where there should be &quot;a security parameters of $k$ bits&quot; or &quot;key size of $k$ bits&quot;. In particular, having RSA and ECC together can only mean that a confusion is made between security in bits (that I now note $b$) and key size $k$. As an aside, the quote uses $\mathcal{O}$ where formally there should be $\Theta$ or $\Omega$, see this for the difference. That's a common, I do it often!
Let's independently derive the cost counted as instructions on standard computers with fixed-width word (as customary), for $b$-bit security meaning $\Theta(2^b)$ work for an attacker to break the system,
Consider RSA with $k$-bit public modulus, and ElGamal as originally formulated, that is the group $\Bbb Z_p^*$ with $p$ a $k$-bit public prime and a generator for all or most of the group. The cost of the private-key operation is dominated by $\Theta(k)$ modular multiplications. Each of these has costs $\Theta(k^2)$ work using common algorithms, $\Theta(k^{\approx1.6})$ for large parameters with Karatsuba, $\Theta(k^{\approx1.5})$ for huge parameters with Toom-Cook, $\Theta(k\log k)$ in theory only. Ignoring anything better than Toom-Cook, we get $\Theta(k^3)$ to $\Theta(k^{2.5})$ work. For RSA, subtract $1$ from the exponent for public-key use (encryption, signature verification) and fixed public exponent.
The two algorithms considered are vulnerable to GNFS, with heuristic cost $L_{(2^k)}\left[1/3,\sqrt[3]{64/9}\,\right]$ in L-notation. Assuming this remains the best attack, and keeping only the first parameter in the interest of simplicity and a little safety margin (from the standpoint of the legitimate user), we have like $\Theta(k^{1/3})$-bit security.
At $b$-bit security, the work for ElGamal as originally formulated, and RSA signature/decryption, thus comes out roughly as $\Theta(b^9)$ to $\Theta(b^{7.5})$.