Problems regarding the equations for work done and kinetic energy For example consider that I am driving a car with a mass of $200$ kg moving at $10$ m/s relative to an outside observer, with an assumed constant opposing friction of $50$ N, for simplicity (it won't make much of a difference in my main point). I then press the pedal to exert a force of $100$ N for 2 seconds. After using $F=ma$ and $s = ut+(1/2)at^2$, the distance traveled within these $2$ seconds can be calculated as $20.5$ m. So the work done would be:
$$W = F  d$$
$$W = 100 \times20.5 = 2050 J$$
If I applied the same force for the same time if the car was not moving at first, it would result in a much smaller value for work done because the distance covered would be less. To be exact it would be:
$$W = 100 \times 0.5 = 50 J$$
In both cases I'm pressing the pedal the same way, for the same duration, so the amount of chemical energy converted from fuel is the same. But then how is there such a big difference in the change in kinetic energy depending on the speed? The first result is 41 times the second result. That would mean that if the kinetic energy calculated were equal to the chemical energy ignited from the fuel, going from 10m/s to 10.5m/s would require 41 times more fuel than going from 0 to 0.5m/s. This is considering there is no energy loss, but even if there were, the energy loss wouldn't even be close to the same degree as calculated, and the values would still be proportional. There is no increase in potential energy as well. But the law of conservation of energy has to be true. To elaborate further, if W =Fd were converted to a function of force and time it would become:
$$W = Fut + F^2t^2/2m$$
Where u is initial velocity, which is frame dependent. This shows that according to the equation, W will change with the initial velocity and the frame of reference, is a quadratic function of force and time, and strangely, inversely related to the mass. The contradiction here is that this implies the same amount of fuel will appear to have different energies depending on the frame
I would also like to point out that the equation for kinetic energy is derived from the equation for work done. So then does the equation for work done and kinetic energy have problems/limitations? Should work done be rather represented as a function of force and time and modified further?
Update: This might be like answering my own question here, but in the equation for W that I have derived, only the first half is velocity and frame dependent. If that part is removed then W becomes independent of frame, so one of the contradictions goes away.
So it would be:
$$W = F^2t^2/2m $$
This equation reduces to W=Fd at 0 initial velocity and if you derive kinetic energy from this formula, it still gives K.E. = 1/2mv^2, which probably means that the equation for K.E. is correct. Is this an appropriate solution?
 A: You have hit upon the apparent paradox of the Oberth effect, and it is discussed in some detail here and here.
Tl;dr: No, the formula $W = F\cdot s$ is correct for a constant force.

What this really amounts to is the fact that kinetic energy is a non-linear function of the velocity. Let us look at your problem from the viewpoint of energy.
If the car initially has velocity $v_0 = 10$m/s, and you push with a net force of $50$N for $2$s, it's final velocity is $v = v_0+at = 10.5$m/s.
If the initial velocity is zero then $v_0 = 0$m/s, and the final velocity is $0.5$m/s.
So the change in velocity is the same in both scenarios, but the change in kinetic energy is hugely different!
In the first scenario, the gain in kinetic energy is:
$$
\frac{1}{2}m(v^2-v_0^2) = 100\cdot(10.5^2-10^2 ) = 1025\ \mathrm{J}
$$
In the second scenario however:
$$
\frac{1}{2}m(v^2-v_0^2) = 100(0.5^2) = 25\ \mathrm{J}
$$
Which is perfectly consistent with your calculation (half the work you do goes to friction, the other half to increasing the kinetic energy).
So why is the kinetic energy a quadratic function of velocity? This may at first seem counter-intuitive (see the "paradox" section of the Wikipedia article on the Oberth effect). But the crucial thing is that energy is relative to frames of reference. This is true for potential energy (what your potential energy is depends on what you define as zero, at least in non-relativistic physics). But it is equally true for kinetic energy: the kinetic energy depends on what frame you choose, e.g. which velocity you are moving. This is consistent, because energy is not absolute, and you can only measure energy differences. Thus, you have to be careful which frame you work in (the same is true for gravitational energy).
So it is consistent with frame invariance to have a kinetic energy which is a quadratic function of velocity. Is it intuitive? Well, that depends on your intuition.

One final comment: real-life spoils this a little bit, because of the difference between static and dynamic friction. If you start an object from zero velocity with respect to the ground, you first have to overcome static friction, which tends to be larger than dynamic friction. Thus, it will be somewhat harder to get an object moving initially than you may expect.
A: 
So doesn't the equation need to account for initial velocity as well?

No, the difference that you posted is in fact correct. We want the same force to give different values for work in the different cases.
The purpose of work is to quantify a transfer of energy from one system to another. Recall that kinetic energy is $KE=\frac{1}{2}mv^2$. So if you start from a higher initial velocity then the change in KE is larger.
Since the change in KE is larger it is necessary that the work also be larger. The issue that you found is therefore not an accident nor a mistake. It is a necessary feature of work for it to serve as a measure of the transfer of energy, which is the whole reason we are interested in the quantity.
A: Several answers have simply been affirming that $K := \frac{1}{2}mv^2$ is the appropriate definition and alluded to the Oberth effect (which this isn't quite), but I don't think they've addressed the crux of your issue, namely the apparent violation of energy conservation.
The issue you've laid out is that, since you have pressed the pedal at the same level for the same time in both scenarios of differing initial velocity, the engine is exerting the same uniform force, and expending the same chemical energy in doing so, yet the kinetic energy increases by much more when the initial velocity is larger. Where did the additional energy come from in the latter scenario, then? Could it be that our formulation of kinetic and chemical energies isn't describing all of the energy present?
As in most cases where one is driven to ask "is our understanding of physics and energy utterly wrong?" when reviewing simple classical systems, the answer is, of course, "No". The mistake in your conception of the problem is that the engine does not expend the same chemical energy per unit time simply because it is imparting the same force. To see why, we simply need to consider the basic picture of how an internal combustion engine works:

Upon each rotation of the crankshaft, the piston in the engine moves up, compressing fuel and air before it is ignited to push the piston back down, accelerating the crankshaft through another turn. Clearly, the expenditure of chemical energy occurs during the ignition of the fuel-air mixture. The expenditure of chemical energy per unit time while maintaining a constant torque on the crankshaft (or constant translational force on the car from friction with the ground), then, is proportional to the ignitions per second, which is exactly the rotations per second of the crankshaft. But the rotational rate of the crankshaft is proportional (depending on the gear) to the speed of the car-- the faster the car is going relative the ground, the faster its wheels turn, and the faster the crankshaft turns. Putting these together, the chemical energy expended per unit time (while maintaining a constant force) is proportional to the speed of the car.
Lo and behold, the kinetic energy per unit time gained by the car according to $K = \frac{1}{2} mv^2$ is exactly
$$\frac{d}{dt} K = m\vec{v} \cdot \frac{d \vec{v}}{dt} = m\vec{a} \cdot \vec{v} = \vec{F}_\text{net} \cdot \vec{v},$$
or the power gained in kinetic energy is $P = Fv$ for one-dimensional motion, also proportional to the speed of the car when the force is fixed.
Indeed, notice that the average speeds in your two scenarios are $0.25$ m/s and $10.25$ m/s, which have a ratio of $41$, so the chemical energies expended should also have a ratio of $41$, as you've found the gained kinetic energies do.
(Image Credit)
