efficient

In the context of computer science, "efficient" means computable in polynomial time with respect to the size of the input. In other words, an algorithm is efficient if on input of size n it terminates after p(n) steps where p() is some polynomial.

There are lots of hard problems for which no efficient solution is known. Factoring, for example. The best algorithm we have (the Number Field Sieve) is exponential time. In other words, to factor an n bit number takes about cⁿ steps for some c in the worst case.

How big is this difference? Humongous. For example, you can run an n³ (O(n³)) algorithm on an input of size 1000 trivially on a personal computer. The same input to an exponential time algorithm would take far more steps to complete than there are atoms in the universe.

Note to CS people: I've obviously swept some details under the rug.

Ef*fi"cient (?), a. [L. efficiens, -entis, p. pr. of efficere to effect: cf. F. efficient. See Effect, n.]

Causing effects; producing results; that makes the effect to be what it is; actively operative; not inactive, slack, or incapable; characterized by energetic and useful activity; as, an efficient officer, power.

The efficient cause is the working cause. Wilson.

Syn. -- Effective; effectual; competent; able; capable; material; potent.

 

© Webster 1913.

---

Ef*fi"cient (?), n.

An efficient cause; a prime mover.

God . . . moveth mere natural agents as an efficient only. Hooker.

 

© Webster 1913.