December 31, 2011

Cloud Computing Explained

Let's say you're an executive at a large corporation. Your particular responsibilities include making sure that all of your employees have the right hardware and software they need to do their jobs. Buying computers for everyone isn't enough -- you also have to purchase software or software licenses to give employees the tools they require.

Whenever you have a new hire, you have to buy more software or make sure your current software license allows another user. It's so stressful that you find it difficult to go to sleep on your huge pile of money every night. Soon, there may be an alternative for executives like you. Instead of installing a suite of software for each computer, you'd only have to load one application. That application would allow workers to log into a Web-based service which hosts all the programs the user would need for his or her job.

Remote machines owned by another company would run everything from e-mail to word processing to complex data analysis programs. It's called cloud computing, and it could change the entire computer industry. In a cloud computing system, there's a significant workload shift. Local computers no longer have to do all the heavy lifting when it comes to running applications. The network of computers that make up the cloud handles them instead. Hardware and software demands on the user's side decrease. The only thing the user's computer needs to be able to run is the cloud computing system's interface software, which can be as simple as a Web browser, and the cloud's network takes care of the rest.

December 1, 2011

Your New Facebook Status: 63,206 Characters or Less

Twitter, as everyone and their tweeting dog knows, limits your status updates to 140 characters. But Facebook? Facebook laughs in the face of such limitations. On Facebook, 140 characters is barely clearing your throat. In a blog post Wednesday, Facebook’s Journalist Program Manager (and Mashable alum) Vadim Lavrusik announced that the limit of Facebook status updates has now been upped to “more than 60,000 characters.” When Mashable asked, Lavrusik explained what that meant, exactly: You can now post a status update measuring 63,206 characters.

But not one character more than that. Sorry, would-be Facebook novelists; you’ll have to split your prose into multiple updates. (As Lavrusik points out, an average novel will now require nine status updates.) This also goes for group messages and posts on your friends’ walls — so you can now annoy the heck out of them with unreasonably long catch-up messages.

Facebook update character limits have been expanding almost as rapidly as the social network itself. Until March 2009, the limit was barely bigger than Twitter’s, at 160 characters. Then 420 characters marked the end of your post’s potential. This summer, it jumped from 500 to 5,000, and now the limit has hit the stratosphere.
So much for social media keeping things short and sweet. At least one Facebook user has already attempted a status update with 60,000 characters of nonsense words, but he’ll need to add 3,206 more to hit the limit.

November 23, 2011

Sabeer Bhatia launches free SMS app Jaxtr

Sabeer Bhatia, the founder of Hotmail.com, on Tuesday launched JaxtrSMS, a mobile application that lets users send unlimited free text messages to any other phone anywhere in the world.
He claimed JaxtrSMS is the world's first mobile-based application for sending SMS that is completely open as the recipients do not need to have the app installed

It is already available as a free download for all major mobile operating systems - iOS, Android, Blackberry and J2ME. In fact, users in 197 countries have already downloaded the app within a few weeks since the soft launch, said Bhatia, who is CEO & co-founded Jaxtr with Yogesh Patel in US. JaxtrSMS is unique in that a mobile user can send a text SMS to any mobile phone in the world without requiring the receiver to have the JaxtrSMS application installed on her phone. This "open" facet of JaxtrSMS distinguishes it from other free mobile messaging applications such as Whatsapp where messages can only be sent within a closed network to people who also have the same app installed. JaxtrSMS retains the number of the user and no new number is required while signing up for the JaxtrSMS service.

"15 years ago, we gave you Hotmail.com, the world's first webmail service that freed up e-mail from the confines of the desktop and aided the creation of a global communications network which was completely open and free for users. Today, we present JaxtrSMS which does to SMS what Hotmail did for e-mail. Now, mobile users can leverage our free and open application to send messages to their contacts anywhere across the world without having to pay anything," said Bhatia. "JaxtrSMS was completely developed in India. I am proud to showcase this as an example of Indian innovation and ingenuity," said Yogesh Patel, president & co-founder

November 20, 2011

Red Hat Enterprise Virtualization 3.0 Beta Available

Red Hat has just announced the availability of its Red Hat Enterprise Virtualization (RHEV) 3.0 public beta. This release, open to all, brings an updated KVM hypervisor based on Red Hat Enterprise Linux 6 and scales to 128 logical CPUs and 2TB of memory for host machines.

With the latest beta, Red hat has updated its RHEV Manager application to a Java app running on JBoss. RHEV 3.0 now has a 'power user portal' that allows users to provision VMs and define VM templates.

Another important addition to RHEV 3.0 is a RESTful API that can be used to manage and configure 'all aspects' of RHEV 3.0. It also sports a new reporting engine for analysis of usage trends, and to produce utilization reports. For companies using RHEV as part of their virtual desktop infrastructure (VDI), Red Hat has added some optimizations around WAN access that include better compression and automatic tuning for desktop color depth and effects.

The first beta of RHEV 3.0 was announced in August, but was not available to the general public. You needed to have an active RHEV subscription at that time. The evaluation is immediately available to anyone with a Red Hat Network account.

The installation and testing is a bit more complex than just slapping RHEL onto a server. To run the beta with the recommended evaluation, you'll need to have a RHEV manager server, two or more hypervisor servers, and shared storage for the systems. You can run the eval with just a single manager server and a single hypervisor server with local storage, however. The download consists of a RHEL 6 ISO and the RHEV Hypervisor ISO.

If you're getting started with RHEV, you might want to check out a series of posts by Red Hat's Richard W.M. Jones. These were from August when RHEV was first released into beta, but should still prove useful. So, who's downloading the beta tonight?

August 26, 2011

August 12, 2011

Tomcat 7.0 (No JDK required)

Today when i was installing tomcat 6 on my local system i noticed that it didn't asked me to install JDK first like it is use to ask in versions previous than 5.5.Most of us who install Tomcat on our development machines wouldn’t have noticed that Tomcat versions before 5.5 required the full blown Java Development Kit (JDK) to be installed on the machine. Just installing the Java Runtime Environment (JRE) wasn’t enough. The JDK is meant for developers to be able to compile Java programs, and has the development tools such as the compiler, debugger and other development libraries. Tomcat versions prior to 5.5 used the Java compiler that comes with the JDK to compile JSP pages at runtime and consequently required a full blown JDK.

Tomcat versions 5.5 and above have a Java compiler (the Eclipse JDT Java compiler) packaged along with it. Now, this is used to compile the JSP pages dynamically instead of the JDK compiler. Hence, it is enough if we just install JRE starting from Tomcat version 5.5 and above.

July 28, 2011

Java 1.7

I have been reading quite a lot about Java 1.7. There are articles about what's new, some code examples, some benchmark to compare performance with previous version of Java and discussion on when it will be released. I have decided to regroup all I have discovered in this article so that I and maybe you, won't have to spend hours surfing the web to find all this information. Don't hesitate to leave a comment if I missed something.
What's new in Java 1.7?

So what made it through is the following:
§ Strings in switch
§ Automatic Resource Management
§ Improved Type Inference for Generic Instance Creation (diamond)
§ Simplified Varargs Method Invocation
§ An omnibus proposal for better integral literals
§ Language support for Collections
§ Language support for JSR 292

These features are divided in different categories:

VM
§ Compressed 64-bit object pointers
§ Garbage-First GC (G1)
§ JSR 292: VM support for non-Java languages (InvokeDynamic)

lang
§ SR 294: Language and VM support for modular programming
§ JSR 308: Annotations on Java types
§ JSR TBD: Small language enhancements (the Project Coin I was talking about)
§ JSR TBD: Project Lambda

core
§ Modularization (Project Jigsaw)
§ Upgrade class-loader architecture
§ Method to close a URLClassLoader
§ Unicode 5.1
§ Concurrency and collections updates (jsr166y)
§ JSR 203: More new I/O APIs for the Java platform (NIO.2)
§ SCTP (Stream Control Transmission Protocol)
§ SDP (Sockets Direct Protocol)
§ Elliptic-curve cryptography (ECC)

client
§ XRender pipeline for Java 2D
§ Forward-port 6u10 deployment features
§ Create new platform APIs for 6u10 graphics features
§ Nimbus look-and-feel for Swing
§ Swing JLayer component

web
§ Update the XML stack
As you can see there is a lot of stuff. I personally tried the new Garbage Collector (G1) a few months back and was really impressed by the performance. Unfortunately the JVM was crashing every few hours so it couldn't be used for production. This GC is available in Java 1.6 as well but same thing, it crashes every so often.
I think that's it for the new features. Maybe it's a good idea to see some code examples now.

July 23, 2011

Dependency Injection

Java components / classes should be as independent as possible of other Java classes. This increases the possibility to reuse these classes and to test them independently of other classes(Unit Testing). To decouple Java components from other Java components the dependency to a certain other class should get injected into them rather that the class itself creates / finds this object.

A class A has a dependency to class B if class uses class B as a variable.

If dependency injection is used then the class B is given to class A via

the constructor of the class A - this is then called construction injection

a setter - this is then called setter injection

The general concept between dependency injection is called Inversion of Control. A class should not configure itself but should be configured from outside.

A design based on independent classes / components increases the re-usability and possibility to test the software. For example if a class A expects a Dao (Data Access object) for receiving the data from a database you can easily create another test object which mocks the database connection and inject this object into A to test A without having an actual database connection.

A software design based on dependency injection is possible with standard Java.

July 20, 2011

Google+ Approaches 18 Million Users

Google+ continues to set records as the fastest-growing social network in history, but Google’s social juggernaut is beginning to show signs that it’s losing steam.

Ancestry.com co-founder Paul Allen (not to be confused with the Microsoft co-founder of the same name) posted his most recent analysis of Google+’s growth on his Google+ account Tuesday. According to his analysis, the search giant’s Facebook competitor will likely reach 18 million users by the end of Tuesday, but its growth rate has dropped by 50% from its peak.

“Last week we saw two days where more than 2 million signed up in a single day,” Allen said in his post. “If that rate had continued, Google+ would have reached 20 million users by last Sunday night. But the last four days have averaged only 948,000 new users, and yesterday the site added only 763,000. Yesterday’s growth of 4.47% was the slowest viral growth since Google opened up invites back on July 6.”

Why is Google+’s growth slowing down? Google Trends indicates that the buzz around Google+ has died down some, which is natural for any major news item. Allen makes the important point that Google+ hasn’t been promoted by any of its other properties and that the social network is still invite-only. Once Google+ is promoted on YouTube or on Google.com, its growth may simply skyrocket.

Allen estimated that Google+ hit the 10 million user mark sometime on July 12 or 13. Google CEO Larry Page confirmed that Google+ had more than 10 million users during an investor earnings call on July 14. Its most followed user, Mark Zuckerberg, now has more than 250,000 followers, despite not posting a single public item on his Google+ account.

July 19, 2011

Review on Golfakademie

Golf Platzreife means "Complete and utter load of bollocks" in English and I will tell you why.

The idea behind it is that you answer a few questions about golf rules and then play a few holes of golf with your instructor. As long as you do not kill too many people whilst playing then you get your 54 handicap... Seriously.. 54 handicap. Basically a 54 handicap means you cannot actually play golf at all and should not really be allowed on a half-decent golf course... But everybody must start somewhere I suppose.....

Since many people are interested in learning the game, there are many golf academies newly erecting in and around the city. Golf academies bear the responsibility to teach the young generation about the game. The rules of the golf etiquette are the first and fore most things, the golf academies teach their students. The rules of the game mainly aim at the safety of the golfers and to the pace of the play, which helps in keeping the game enjoyable. The golf etiquette is an essential part of the game. This is something very vital that all the new comers and the new beginners should learn on the course.

For any game to be played successfully, the instruments used for the play should be manufactured or prepared with utmost care and you can found all these instruments at their Golf shop. A standard set of a golf club mainly consists of three woods, eight irons and a putter. Actually according to the rules and regulations of the play a golfer is allowed to carry 14 clubs in the bag. The more clubs the player carries the easier is his victory. To know more about golf academies, please visit Golfreisen.
The above site explains you all the details about the game. They are one of the largest German golf shops with a full range of all brand names. You can also visit Golfkurse it will be useful for you.

July 13, 2011

Importing a class from default package - Impossible

Did you know that classes in the ‘default package’ (classes that don’t have a package) cannot be imported from classes that do have a package?

I did not know that.

Try it:



Now try to compile your code:
>javac Class1.java

>javac package2\Clazz2.java -cp .

package2\Clazz2.java:3: ‘.’ expected
import Class1;
^
package2\Clazz2.java:3: ‘;’ expected
import Class1;

How stupid is this?
Is this why omitting package is deprecated?

May 18, 2011

MVC1 Vs MVC2

A MVC Model 1 architecture consists of a Web browser directly accessing Web-tier JSP pages. The JSP pages access Web-tier JavaBeans that represent the application model, and the next view to display (JSP page, servlet, HTML page, and so on) is determined either by hyperlinks selected in the source document or by request parameters. A Model 1 application control is decentralized, because the current page being displayed determines the next page to display. In addition, each JSP page or servlet processes its own inputs (parameters from GET or POST). In some Model 1 architectures, choosing the next page to display occurs in scriptlet code, but this usage is considered poor form.

A MVC Model 2 architecture introduces a controller servlet between the browser and the JSP pages or servlet content being delivered. The controller centralizes the logic for dispatching requests to the next view based on the request URL, input parameters, and application state. The controller also handles view selection, which decouples JSP pages and servlets from one another. Model 2 applications are easier to maintain and extend, because views do not refer to each other directly. The Model 2 controller servlet provides a single point of control for security and logging, and often encapsulates incoming data into a form usable by the back-end MVC model. For these reasons, the Model 2 architecture is recommended for most interactive applications.

March 9, 2011

XML Parsers

Evolution of the XML Parsing/Manipulation using Java

The combination of Java and XML has been one of the most attracting things which had happened in the field of software development in the 21st century. It has been mainly for two reasons - Java, arguably the most widely used programming language and XML, almost unarguably the best mechanism of data description and transfer.

Since these two were different technologies and hence it initially required a developer to have a sound understanding of both of these before he can make the best use of the combination. Since then there have been a paradigm shift towards Java and we have seen few interesting technologies getting evolved to make this happen. Some of them are:-

SAX - Simple API for XML Parsing

It was the first to come on the scene and interestingly it was developed in the XML-Dev maling list. Evidently the people who developed this were XML gurus and it is quite visible in the usage of this API. You got to have a fair understanding of XML, but at least Java developers got something to combine the two worlds - Java and XML in a structured way. It instantly became a hit for the obvious reasons.

Being the first in the evolution ladder, it obviously had only the basic support for XML processing. It is an event-based technology, which uses callbacks to load the parts of the XML document in a sequential way. This effectively means you can't go back to some part which was read/processed previously - if you do have such a requirement then you would need to store/manage the relevant data yourself.

Since this API does require to load the entire XML doc and also because it offers only a sequential processing of the doc hence it is quite fast. Another reason of it being faster is that it does not allow modification of the underlying XML data.

Interested in going through a step-by-step implementation (with explanation of the complete source code) of a simple SAX Parser in Java using SAX2 APIs? Here is it for you - SAX Parser Implementation in Java >>

DOM - Document Object Model

The Java binding for DOM provided a tree-based representation of the XML documents - allowing random access and modification of the underlying XML data. Not very difficult to deduce that it would be slower as compared to SAX.

The event-based callback methodology was replaced by an object-oriented in-memory representation of the XML documents. Though, it differs from one implementation to another if the entire document or a part of it would be kept in the memory at a particular instant, but the Java developers are kept out of all the hassle and they get the entire tree readily available whenever they wish.

JAXP - Java API for XML Parsing

The creators and designers of Java realized that the Java developers should not be XML gurus to use the XML in Java applications. The first step towards making this possible was the evolution of JAXP, which made it easier to obtain either a DOM Document or a SAX-compliant parser via a factory class. This reduced the dependence of Java developers over the numerous vendors supplying the parsers of either type. Additionally, JAXP made sure that an interchange between the parsers required minimal code changes.


February 23, 2011

How Scrollable ResultSets Work?

JDBC result sets are created with three properties: type, concurrency and holdability.
The type can be one of
-TYPE_FORWARD_ONLY
-TYPE_SCROLL_INSENSITIVE
-TYPE_SCROLL_SENSITIVE.

The concurrency can be one of
-CONCUR_READ_ONLY
-CONCUR_UPDATABLE.

The holdability can be one of
-HOLD_CURSORS_OVER_COMMIT
-CLOSE_CURSORS_AT_COMMIT.

JDBC allows the full cross product of these. Some database like SQL 2003 prohibits the combination {TYPE_SCROLL_INSENSITIVE, CONCUR_UPDATABLE}, but this combination is supported by some vendors, notably Oracle.

The movable cursors,moving forward and backward on a resultset is one of the new features in the JDBC 2.0 API. There are also methods that let you move the cursor to a particular row and check the position of the cursor.
Statement stmt = con.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_READ_ONLY);

ResultSet resultSet = stmt.executeQuery("SELECT FNAME, LNAME FROM EMPLOYEE");

while (resultSet.next()) {

. . . // iterates forward through resultSet

}

. . .

resultSet.absolute(5); // moves cursor to the fifth row

. . .

resultSet.relative(-2); // moves cursor to the third row

. . .

resultSet.relative(4); // moves cursor to the seventh row

. . .

resultSet.previous(); // moves cursor to sixth row

. . .

int rowNumber = resultSet.getRow(); // rowNumber should be 6

resultSet.moveAfterLast(); // moves cursor to position // after last row

while (previous()) {

. . . // iterates backward through resultSet

}

When a resultset type is defined then it is also significant to define whether it is readonly or updatable and type and concurrency should be in the same order as shown in the code above.If you change the order then compiler can not distinguish it.If you specify the constant TYPE_FORWARD_ONLY, it creates a nonscrollable result set, in which the cursor moves forward only. The default value of ResultSet object type is TYPE_FORWARD_ONLY and CONCUR_READ_ONLY.

February 22, 2011

How JVM handles thread synchronization?

JVM associates a lock with an object or a class to achieve mutilthreading. A lock is like a token or privilege that only one thread can "possess" at any one time. When a thread wants to lock a particular object or class, it asks the JVM.JVM responds to thread with a lock maybe very soon, maybe later, or never. When the thread no longer needs the lock, it returns it to the JVM. If another thread has requested the same lock, the JVM passes the lock to that thread.If a thread has a lock,no other thread can access the locked data until the thread that owns the lock releases it.

The JVM uses locks in conjunction with monitors. A monitor is basically a guardian in that it watches over a sequence of code, making sure only one thread at a time executes the code.Each monitor is associated with an object reference. It is the responsibility of monitor to watch an arriving thread must obtain a lock on the referenced object.

When the thread leaves the block,it releases the lock on the associated object.A single thread is allowed to lock the same object multiple times.JVM maintains a count of the number of times the object has been locked. An unlocked object has a count of zero. When a thread acquires the lock for the first time, the count is incremented to one. Each time the thread acquires a lock on the same object, a count is incremented. Each time the thread releases the lock, the count is decremented. When the count reaches zero, the lock is released and made available to other threads.

In Java language terminology, the coordination of multiple threads that must access shared data is called synchronization. The language provides two built-in ways to synchronize access to data: with synchronized statements or synchronized methods.

The JVM does not use any special opcodes to invoke or return from synchronized methods. When the JVM resolves the symbolic reference to a method, it determines whether the method is synchronized. If it is, the JVM acquires a lock before invoking the method. For an instance method, the JVM acquires the lock associated with the object upon which the method is being invoked. For a class method, it acquires the lock associated with the class to which the method belongs. After a synchronized method completes, whether it completes by returning or by throwing an exception, the lock is released.

Two opcodes, monitorenter and monitorexit are used by JVM for accomplishing this task.

When monitorenter is encountered by the Java virtual machine, it acquires the lock for the object referred to by objectref on the stack. If the thread already owns the lock for that object, a count is incremented. Each time monitorexit is executed for the thread on the object, the count is decremented. When the count reaches zero, the monitor is released.

Story of a Java Program from start to end

When JVM executes a Java application, a runtime instance of JVM is born.This runtime instance invoke main() method of Java application.The main() method of an application serves as the starting point for that application's initial thread. The initial thread can in turn fire off other threads.

This thread has a program counter(PC) and Java stack.Whenever main() method is invoked, a stack frame is pushed onto the stack,this then becomes the active tack frame.The program counter in the new Java stack frame will point to the beginning of the method.

If there are more method invocations within main() method then this process of pushing new stack frame onto the stack for each method call is repeated as and when they are invoked.When a method returns, the active frame is popped from the stack and the one below becomes the active stack frame.The PC is set to the instruction after the method call and the method continues.

There is only one heap corresponding to an instance of JVM and all objects created are stored here.This heap is shared by all threads created in an application.

Inside the Java virtual machine, threads come in two flavors: daemon and non- daemon. A daemon thread is ordinarily a thread used by the virtual machine itself, such as a thread that performs garbage collection. The application, however, can mark any threads it creates as daemon threads. The initial thread of an application--the one that begins at main()--is a non- daemon thread.

A Java application continues to execute (the virtual machine instance continues to live) as long as any non-daemon threads are still running. When all non-daemon threads of a Java application terminate, the virtual machine instance will exit. If permitted by the security manager, the application can also cause its own demise by invoking the exit() method of class Runtime or System.

When main() returns,it terminates the application's only non-daemon thread, which causes the virtual machine instance to exit.

February 4, 2011

Time Complexity of Algorithms

From my college days, I always found myself struggling with Algorithms,their complexities,asymptotic notations and blah blah blah and still. But now after reading a lot of articles on this I can say that I learnt something. So, whatever I had learnt till now I am going to post it here for my future reference and for other geeks who are at the same place where I was few years back.

(Specifically for Beginners)May be you found this post very slow,but once u finished I am sure that today u had learnt something new.



If you feel like reading this post slowly and carefully, it will describe what this notation _really_ means.

All functions have some kind of behavior as n grows towards infinity. For example, if f(n) = 1/n, then as n grows towards infinity, f(n) gets closer and closer to zero. Whereas if f(n) = n*n, then as n grows towards infinity, f(n) grows too.

Functions can grow at different speeds. If two functions are equal, then they obviously grow at the same speed. But wait, there's more! Two functions are deemed to grow at the same speed if they're separated by a constant multiple! For example, if f(n) = n*n and g(n) = 3*n*n, then f and g are deemed to grow at the same pace, because g(n) = 3*f(n), so they are only a constant multiple apart. That is, g(n) / f(n) = 3, as n grows arbitrarily large.

But consider the scenario where f(n) = n * n, and g(n) = n. Then what is the behavior of f(n) and g(n) as n grows arbitrarily large? Well, f(n) / g(n) = (n * n) / (n). Which simplifies to f(n) / g(n) = n. Which means that as n grows large, f(n) = n * g(n). What does this mean? f and g are in this case not separated by a constant multiple. The multiple between f and g grows larger and larger as time progresses, without stopping. We say that "f grows faster than g" when this happens. Or "g grows slower than f". Just try some sample values of n: Try 10, 100, and 1000. First, f(10) / g(10) = 100 / 10 = 10. f(100) / g(100) = 10000 / 100 = 100. f(1000) / g(1000) = 1000000 / 1000 = 1000. We can easily see, hopefully, that the ratio between f and g is not constant.

Now consider the scenario where f(n) = 2 * n * n + 1, and g(n) = n * n. In this case, our functions have the ratio f(n) / g(n) = (2 * n * n + 1) / (n * n). What is the value of this ratio as n grows towards infinity? The answer is 2. Let's simplify the expression:

(2 * n * n + 1) / (n * n) =
(2 * n * n) / (n * n) + 1 / (n * n) =
2 + 1 / (n * n).

So f(n) / g(n) = 2 + 1 / (n * n).

So as n grows large, the term 1 / (n * n) gets arbitrarily (or rediculously) small. As n grows large, then, the value of (2 + 1 / n * n) gets closer and closer to 2.

We could plug in some values -- let's try 10, 100, and 1000 again.

f(10) / g(10) = (2 * 10 * 10 + 1) / (10 * 10) = 201 / 100 = 2.01
f(100) / g(100) = (2 * 100 * 100 + 1) / (100 * 100) = 20001 / 10000 = 2.0001
f(1000) / g(1000) = (2 * 1000 * 1000 + 1) / (1000 * 1000) = 2000001 / 1000000 = 2.0000001.

So the ratio between these two functions approaches a constant value as n grows large. Hence, f and g are said to grow at the same pace.

In comparing the growth rates of functions, we have these rules:

1. If f(n) / g(n) grows out of control, getting larger and larger as n gets larger, then f is said to grow faster than g.
2. If f(n) / g(n) settles towards some constant positive value, then f is said to grow at the same pace as g.
3. If f(n) / g(n) gets closer and closer to zero, then this means that its reciprocal, g(n) / f(n), is growing out of control, so g is said to grow faster than f. (Or f is said to grow slower than g.)


Now on to big O notation!

Big O notation actually refers to an entire _set_ of functions. The notation O(expression) represents the entire set of functions that grow slower than or at the same pace as expression. For example, O(n^2) represents the entire set of functions that grow slower than or at the same pace as n^2.

In other words, if g(n) = n, then since n grows slower than n^2, it follows that g lies in the set O(n^2). Likewise, if h(n) = 2 * n * n + 1, then since h grows at the same pace as n^2, it follows that h lies in the set O(n^2).

It's also true that h lies in the set O(n^3), because h grows slower than n^3. (Assuming the leading term is positive, quadratic functions always grow slower than cubic polynomials, which always grow slower than fourth-degree polynomials, which always grow slower than fifth-degree polynomials, and so on.)

Because O(expression) represents all the functions that grow _slower_ than or equal to expression, it is used to represent upper bounds.

The other notations refer to different sets of functions. For example, o(expression) represents all the functions that grow slower than expression (and not at the same speed.) f(n) = n^2 + n - 1 lies in the set O(n^2), but it doesn't lie in o(n^2). g(n) = n lies in both.

Theta(expression) represents all the functions that grow at the same rate as expression.

Omega(expression) represents all the functions that grow faster than or equal to expression.

In computer programs, we are of course interested in how much time it takes programs to run, and these forms of notation are useful for representing that, so that's why we use them. When you say an algorithm runs in O(expression) time, you're just saying that the algorithm's runtime is no worse than some multiple of expression. When you use Theta, you're saying that the algorithm's runtime is some multiple of expression. And Omega is used to say that the amount of time an algorithm takes to run grows at a rate that is larger than or equal to some expression's rate of growth.

Please feel free to post any comment or suggestions ...

Cheers!!!
 

Copyright 2007 All Right Reserved. shine-on design by Nurudin Jauhari. and Published on Free Templates