You can do $2^{30}$ encryptions per second and the key size is 64 bits.
$2^{64}/2^{30}$ should give me the time taken for a brute force attack? What if you double the key size?
How can I calculate the maximum and average time taken for such an attack.
Well, that's simple: $2^{64}/2^{30}$ is indeed correct. And since $2^{64}/2^{30} = 2^{64 - 30} = 2^{34}$ then that would be the answer. A simple recalculation would give you approximately 545 years. As you can see, 64 bits is pretty much on the border of being cracked by general computers. It is also about the same size as the SHAttered attack; these kind of attacks scale well, so just renting 640 cores for a year in a cloud service would probably do it.
Brute force basically scales linearly with the amount of keys. However, we're doubling the key size here, not the amount of keys. Growing the key size exponentially grows the amount of possible keys. It's a bigger step to go from 10 to 100 as it is to go from 1 to 10, both in decimals as in binary calculations.
545 years would however be the maximum time it would take to find a key by trying all of them. On average you'd need half of that time using a single core as the key may be either on the lower half or higher half of the key space (whichever way you split it in two equal size parts, as each key should be equally likely). Each additional bit in the key size doubles the key space. That means you could subtract a single bit from the key size to find out the average time it costs to brute force the key.
The calculation required to find out the time it takes to brute force a 128 bit key isn't that more complicated: $2^{2 \cdot 64}/2^{30} = 2^{128}/2^{30} = 2^{128 - 30} = 2^{98}$. The outcome of course is rather different though; you'd now need $10^{22}$ years. Or around 700 billion times the current life-time of the universe to try all the keys. Or 350 billion times the life of the universe if you average things out (yeah, right).
Then again, according to WolframAlpha $10^{22}$ years is only 3.3 times the half life of Calcium-76 so there may be some calcium atoms left to witness the end result. Again, you can drastically reduce the time by adding processors. However, you'd need too much processors and energy to bring it back to a value that is possible to crack in a life time. Better not try to brute force a properly randomized 128 bit key then.
Important: it may be that you're not trying to find the value of a single key, but you're trying to find the value of one of a million keys. This, of course, it much easier because the chance of finding one quickly increases. This, and the possible advance of quantum computing, may be enough reason to go for a 256 bit key strength.
@MaartenBodewes's using the observation that "the key may be either on the lower half or higher half of the key space" to derive the average time is very clever.
In my answer, I want to give a quite standard approach to calculate the average time. Let $T$ be the random variable of the time needed to find the key. Then the average time is the expectation of $T$, $$ \mathrm{E}[T] = \sum_{t} t \cdot \mathrm{Pr}[T=t]. $$ Let $N = 2^n$ be the number of all possible keys. Assume that the brute force attacker can test $M$ keys per second, then the time needed to test $i$ keys is $\frac{i}{M}$. In order for $T = \frac{i}{M}$, the previous $i-1$ tests must all have failed, and the key is found exactly in the $i^{\text{th}}$ test.
In the $j^{\text{th}}$ test, we have tested $j-1$ keys, and there are $N-j+1$ keys left for examination.
Therefore, the probability of succeeding after the $i^{\text{th}}$ test, $\mathrm{Pr}[T = \frac{i}{M}]$, is (when $i \ge 2$) $$ \underbrace{ \left(\frac{N-1}{N} \times \frac{N-2}{N-1} \times \dots \times \frac{N-i+1}{N-i+2}\right) }_{\text{the previous } i-1 \text{ tests failed}} \times \underbrace{\frac{1}{N-i+1}}_{\text{the } i^{\text{th}} \text{ succeeds}} = \frac{1}{N} $$ One can verify that it still holds when $i < 2$.
Hence, $$ \mathrm{E}[T] = \sum_{i=1}^{N} \frac{i}{M} \cdot \frac{1}{N} = \frac{1}{MN} \cdot \frac{N(N+1)}{2} = \frac{N+1}{2M} \approx \frac{N}{2M} $$ , which is approximately one half of the worst case time: $\frac{N}{M}$.
