Plain English explanation of Big O

Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is a two-side bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

---

The simplest definition I can give for Big-O notation is this:

Big-O notation is a relative representation of the complexity of an algorithm.

There are some important and deliberately chosen words in that sentence:

• relative: you can only compare apples to apples. You can't compare an algorithm to do arithmetic multiplication to an algorithm that sorts a list of integers. But two algorithms that do arithmetic operations (one multiplication, one addition) will tell you something meaningful;
• representation: Big-O (in its simplest form) reduces the comparison between algorithms to a single variable. That variable is chosen based on observations or assumptions. For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). This assumes that comparison is expensive. But what if comparison is cheap but swapping is expensive? It changes the comparison; and
• complexity: if it takes me one second to sort 10,000 elements how long will it take me to sort one million? Complexity in this instance is a relative measure to something else.

Come back and reread the above when you've read the rest.

The best example of Big-O I can think of is doing arithmetic. Take two numbers (123456 and 789012). The basic arithmetic operations we learnt in school were:

• addition;
• subtraction;
• multiplication; and
• division.

Each of these is an operation or a problem. A method of solving these is called an algorithm.

Addition is the simplest. You line the numbers up (to the right) and add the digits in a column writing the last number of that addition in the result. The 'tens' part of that number is carried over to the next column.

Let's assume that the addition of these numbers is the most expensive operation in this algorithm. It stands to reason that to add these two numbers together we have to add together 6 digits (and possibly carry a 7th). If we add two 100 digit numbers together we have to do 100 additions. If we add two 10,000 digit numbers we have to do 10,000 additions.

See the pattern? The complexity (being the number of operations) is directly proportional to the number of digits n in the larger number. We call this O(n) or linear complexity.

Subtraction is similar (except you may need to borrow instead of carry).

Multiplication is different. You line the numbers up, take the first digit in the bottom number and multiply it in turn against each digit in the top number and so on through each digit. So to multiply our two 6 digit numbers we must do 36 multiplications. We may need to do as many as 10 or 11 column adds to get the end result too.

If we have two 100-digit numbers we need to do 10,000 multiplications and 200 adds. For two one million digit numbers we need to do one trillion (10¹²) multiplications and two million adds.

As the algorithm scales with n-squared, this is O(n²) or quadratic complexity. This is a good time to introduce another important concept:

We only care about the most significant portion of complexity.

The astute may have realized that we could express the number of operations as: n² + 2n. But as you saw from our example with two numbers of a million digits apiece, the second term (2n) becomes insignificant (accounting for 0.0002% of the total operations by that stage).

The Telephone Book

The next best example I can think of is the telephone book, normally called the White Pages or similar but it'll vary from country to country. But I'm talking about the one that lists people by surname and then initials or first name, possibly address and then telephone numbers.

Now if you were instructing a computer to look up the phone number for "John Smith" in a telephone book that contains 1,000,000 names, what would you do? Ignoring the fact that you could guess how far in the S's started (let's assume you can't), what would you do?

A typical implementation might be to open up to the middle, take the 500,000^th and compare it to "Smith". If it happens to be "Smith, John", we just got real lucky. Far more likely is that "John Smith" will be before or after that name. If it's after we then divide the last half of the phone book in half and repeat. If it's before then we divide the first half of the phone book in half and repeat. And so on.

This is called a binary search and is used every day in programming whether you realize it or not.

So if you want to find a name in a phone book of a million names you can actually find any name by doing this at most 20 times. In comparing search algorithms we decide that this comparison is our 'n'.

For a phone book of 3 names it takes 2 comparisons (at most).
For 7 it takes at most 3.
For 15 it takes 4.
...
For 1,000,000 it takes 20.

That is staggeringly good isn't it?

In Big-O terms this is O(log n) or logarithmic complexity. Now the logarithm in question could be ln (base e), log₁₀, log₂ or some other base. It doesn't matter it's still O(log n) just like O(2n²) and O(100n²) are still both O(n²).

It's worthwhile at this point to explain that Big O can be used to determine three cases with an algorithm:

• Best Case: In the telephone book search, the best case is that we find the name in one comparison. This is O(1) or constant complexity;
• Expected Case: As discussed above this is O(log n); and
• Worst Case: This is also O(log n).

Normally we don't care about the best case. We're interested in the expected and worst case. Sometimes one or the other of these will be more important.

Back to the telephone book.

What if you have a phone number and want to find a name? The police have a reverse phone book but such lookups are denied to the general public. Or are they? Technically you can reverse lookup a number in an ordinary phone book. How?

You start at the first name and compare the number. If it's a match, great, if not, you move on to the next. You have to do it this way because the phone book is unordered (by phone number anyway).

So to find a name:

• Best Case: O(1);
• Expected Case: O(n) (for 500,000); and
• Worst Case: O(n) (for 1,000,000).

The Travelling Salesman

This is quite a famous problem in computer science and deserves a mention. In this problem you have N towns. Each of those towns is linked to 1 or more other towns by a road of a certain distance. The Travelling Salesman problem is to find the shortest tour that visits every town.

Sounds simple? Think again.

If you have 3 towns A, B and C with roads between all pairs then you could go:

A -> B -> C
A -> C -> B
B -> C -> A
B -> A -> C
C -> A -> B
C -> B -> A

Well actually there's less than that because some of these are equivalent (A -> B -> C and C -> B -> A are equivalent, for example, because they use the same roads, just in reverse).

In actuality there are 3 possibilities.

Take this to 4 towns and you have (iirc) 12 possibilities. With 5 it's 60. 6 becomes 360.

This is a function of a mathematical operation called a factorial. Basically:

5! = 5 * 4 * 3 * 2 * 1 = 120
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
...
25! = 25 * 24 * ... * 2 * 1 = 15,511,210,043,330,985,984,000,000
...
50! = 50 * 49 * ... * 2 * 1 = 3.04140932... × 10^64 

So the Big-O of the Travelling Salesman problem is O(n!) or factorial or combinatorial complexity.

By the time you get to 200 towns there isn't enough time left in the universe to solve the problem with traditional computers.

Something to think about.

Polynomial Time

Another point I wanted to make quick mention of is that any algorithm that has a complexity of O(n^a) is said to have polynomial complexity or is solvable in polynomial time.

Traditional computers can solve polynomial-time problems. Certain things are used in the world because of this. Public Key Cryptography is a prime example. It is computationally hard to find two prime factors of a very large number. If it wasn't, we couldn't use the public key systems we use.

Anyway, that's it for my (hopefully plain English) explanation of Big O (revised).

http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o

Why should i use EJB? [closed]

In the commercial world, EJBs have almost totally been supplanted by Spring. The advantage of Spring is that it can be run inside a simple Web container like Jetty or Tomcat whereas EJBs (pre-3.1) require a J2EE application server (eg Websphere, Weblogic, JBoss, Glassfish), which has a larger footprint.

EJBs do a couple of things well, most especially stateless session beans, which can be an efficient avenue for distributed transactions.

EJB since 3.0 has been split into two parts: the EJB spec and the JPA spec. JPA (Java Persistence API) is as the name suggests the persistence part of the API. This is really commonly used in libraries like EclipseLink, Hibernate and Toplink. Hibernate is the most popular and predates JPA but the differences aren't so large.

JPA is a form of ORM (object-relational mapper) of projecting an object model onto a relational database.

JPA is, in my experience, used much more commonly than EJB.

http://stackoverflow.com/questions/2506915/why-should-i-use-ejb

In Java, what purpose do the keywords `final`, `finally` and `finalize` fulfil?

final

final can be used to mark a variable "unchangeable"

private final String name = "foo";  //the reference name can never change

final can also make a method not "overrideable"

public final String toString() {  return "NULL"; }

final can also make a class not "inheritable". i.e. the class can not be subclasses.

public final class finalClass {...}
public class classNotAllowed extends finalClass {...} // Not allowed

finally

finally is used in a try/catch statement to execute code "always"

lock.lock();
try {
  //do stuff
} catch (SomeException se) {
  //handle se
} finally {
  lock.unlock(); //always executed, even if Exception or Error or se
}

Java 7 has a new try with resources statement that you can use to automatically close resources that explicitly or implicitly implement java.io.Closeable or java.lang.AutoCloseable

finalize

finalize is called when an object is garbage collected. You rarely need to override it. An example:

public void finalize() {
  //free resources (e.g. unallocate memory)
  super.finalize();
}

http://stackoverflow.com/questions/7814688/in-java-what-purpose-do-the-keywords-final-finally-and-finalize-fulfil

What exactly we mean by Precompiled SQL Statement

If a statement is used multiple times in a session, precompiling it provides better performance than sending it to the database and compiling it for each use. The more complex the statement, the greater the performance benefit.
If a statement is likely to be used only a few times, precompiling it may be inefficient because of the overhead involved in precompiling, saving, and later deallocating it in the database.
Precompiling a dynamic SQL statement for execution and saving it in memory uses time and resources. If a statement is not likely to be used multiple times during a session, the costs of doing a database prepare may outweigh its benefits. Another consideration is that once a dynamic SQL statement is prepared in the database, it is very similar to a stored procedure. In some cases, it may be preferable to create stored procedures and have them reside on the server, rather than defining prepared statements in the application.

http://www.coderanch.com/t/299852/JDBC/databases/Precompiled-SQL-Statement

Compile time polymorphism

Hi Rajan,
Thats perfectly right. You need to *understand* the polymorphism concepts first.

Poly - many, morphism - faces.

The ability to have more than one version of the executable piece of code in the same name to invoke is called POLYMORPHISM.

view plaincopy to clipboardprint?

Note: Text content in the code blocks is automatically word-wrapped

1. Actually speaking the compiler would create a binding between the place of calling and the method definition.  

The ability to take a decision and thereby creating the binding is what gives you the name. 

The Compile time polymorphism comes in such a way that the compiler is able to differentiate the exact version of code to invoke during the compile time itself. Rather, the compiler *can take a decision of which exact method to invoke* during the compile time itself. 

Whereas in Runtime Polymorphism, the compiler is unable to take such a decision during compilation. Moreover, compiler-is-left-free-for-that-sake until runtime with which it can decide and invoke the appropriate version of the method.

Only when Inheritance is in picture, you can very well play around with the Polymorphism as you are given the rights to assign the child class objects to any of its parent/super class references. 

I hope this clears your doubt!

What does the Spring framework do? Should I use it? Why or why not? [closed]

What does the Spring framework do? Should I use it? Why or why not?

Spring is a framework that helps you to "wire" different components together. It is most useful in cases where you have a lot of components and you might decide to combine them in different ways, or wish to make it easy to swap out one component for another depending on different settings or environments.

This is what I've always understood "dependency injection" to be.

I would suggest a different definition:

"Dependency injection is where you design your classes so that they expect an outside actor to directly give them the sub-tools they need to do their jobs before anybody starts asking them to do something."

Most of the XML (or annotation-based) stuff is telling spring:

• When someone asks for a "HammerStore", I want you to create a example.HammerStore and return it result. Cache the result, since there is only one store.
• When someone asks for a "SomeHammer", I want you to find a "HammerStore" and return the result of its getHammer() method. Do not cache the result, but make a new hammer each time.
• When someone asks for a "SomeWrench", I want you to create a example.WrenchImpl and take the configuration setting guage and put it into the setWrenchSize() property. Do not cache the result, but create a new one each time.
• When someone asks for a "OurPlumber", I want to you create an instance of example.PlumberImpl. Put the string "Pedro" into its setName() method, put a "SomeHammer" into its setHammer()method, and put a "SomeHammer" into its setWrench() method. Return the result, but do cache it, since we only have one Pedro.

In this way, Spring lets your connect components, label them, control their lifecycle/caching, and alter behavior based on configuration.

To facilitate [testing] I typically make (at least) two versions of a method : one that uses instance variables, and one that only uses variables that are passed in to the method.

That sounds like a lot of overhead for not a lot of benefit for me. I would suggest that you make your instance variables protected or package-level, and then locate the unit tests inside the same package. That way you can alter or test the instance variables in-place.

http://programmers.stackexchange.com/questions/92393/what-does-the-spring-framework-do-should-i-use-it-why-or-why-not

What is an idempotent operation?

In computing, an idempotent operation is one that has no additional effect if it is called more than once with the same input parameters.

Pure functions (those whose return value only depends on the input parameters) are always idempotent (Python syntax examples):

def sq(x):
    return x * x

Functions that only set a value are idempotent:

g_x = 5

def set_x(x):
    global g_x
    g_x = x

However, functions that do something like append to a global list are not idempotent:

a = []

def add_x(x):
    a.append(x)

Idempotent operations are often used in the design of network protocols, where a request to perform an operation is guaranteed to happen at least once, but might also happen more than once. If the operation is idempotent, then there is no harm in performing the operation two or more times.

It is somewhat unfortunate that in mathematics, the use of idempotent is slightly different. See the Wikipedia article on idempotence for more information.

http://stackoverflow.com/questions/1077412/what-is-an-idempotent-operation