Skip to main content

Efficiency of an algorithm

Efficiency of an algorithm

Programmers find a tough time writing efficient code. But what exactly do we mean by efficiency? What difference does it make if we write normal code instead of an efficient code? Let’s find out with a simple example of traditional sorting problem.



    The first, known as insertion sort, takes time roughly equal to c1*n2 to sort n items, where c1 is a constant that does not depend on n. That is, it takes time roughly proportional to n2. The second, merge sort, takes time roughly equal to c2*n lg n, where lg n stands for log2 n and c2 is another constant that also does not depend on n. Insertion sort usually has a smaller constant factor than merge sort, so that c1 < c2. We shall see that the constant factors can be far less significant in the running time than the dependence on the input size n.



    Where merge sort has a factor of lg n in its running time, insertion sort has a factor of n, which is much larger. Although insertion sort is usually faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of lg n vs. n will more than compensate for the difference in constant factors. No matter how much smaller c1 is than c2, there will always be a crossover point beyond which merge sort is faster.


    For a concrete example, let us pit a faster computer (computer A) running insertion sort against a slower computer (computer B) running merge sort. They each must sort an array of one million numbers. Suppose that computer A executes one billion instructions per second and computer B executes only ten million instructions per second, so that computer A is 100 times faster than computer B in raw computing power. To make the difference even more dramatic, suppose that the world’s craftiest programmer codes insertion sort in machine language for computer A, and the resulting code requires 2n2 instructions to sort n numbers. (Here, c1 = 2.) Merge sort, on the other hand, is programmed for computer B by an average programmer using a high-level language with an inefficient compiler, with the resulting code taking 50n lg n instructions (so that c2 = 50).
     To sort one million numbers, computer A takes :
                                  2 · (106)**2 (here ** indicates power) instructions 
                                10**9 instructions/second = 2000 seconds , 
while computer B takes :
                               50 · 10**6 lg 10**6 instructions 
                            10**7 instructions/second ≈ 100 seconds .

 By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runs 20 times faster than computer A! The advantage of merge sort is even more pronounced when we sort ten million numbers: where insertion sort takes approximately 2.3 days, merge sort takes under 20 minutes. In general, as the problem size increases, so does the relative advantage of mergesort.

Comments

Popular posts from this blog

What is context in android ?

The topic of Context in Android seems to be confusing too many. People just know that Context is needed quite often to do basic things in Android. People sometimes panic because they try to do perform some operation that requires the Context and they don’t know how to “get” the right Context. I’m going to try to demystify the idea of Context in Android. A full treatment of the issue is beyond the scope of this post, but I’ll try to give a general overview so that you have a sense of what Context is and how to use it.
What exactly is Context?


Well, the documentation itself provides a rather straightforward explanation: The Context class is an “Interface to global information about an application environment". The Context class itself is declared as abstract class, whose implementation is provided by the Android OS. The documentation further provides that Context “…allows access to application-specific resources and classes, as well as up-calls for application-level operations such as…

LocationManager vs GoogleApiClient

User Location on Android
Getting the user’s location on Android is a little less straightforward than on iOS. To start the confusion, there are two totally different ways you can do it. The first is using Android APIs from android.location.LocationListener, and the second is using Google Play Services APIs com.google.android.gms.location.LocationListener. Let’s go through both of them.
1.Android’s Location API
The Android’s location APIs use three different providers to get location - ·LocationManager.GPS_PROVIDER — This provider determines location using satellites. Depending on conditions, this provider may take a while to return a location fix. ·LocationManager.NETWORK_PROVIDER — This provider determines location based on availability of cell tower and WiFi access points. Results are retrieved by means of a network lookup. ·LocationManager.PASSIVE_PROVIDER — This provider will return locations generated by other providers. You passively receive location updates …

ANGULAR-2

Angular JS is an open source framework built on JavaScript. It was built by the
developers at Google. This framework was used to overcome obstacles encountered while
working with Single Page applications. Also, testing was considered as a key aspect while
building the framework. It was ensured that the framework could be easily tested. The
initial release of the framework was in October 2010.

Features of Angular 2:Components: The earlier version of Angular had a focus of Controllers but now has changed the focus to having components over controllers. Components help to
build the applications into many modules. This helps in better maintaining the
application over a period of time.

TypeScript: The newer version of Angular is based on TypeScript. This is a
superset of JavaScript and is maintained by Microsoft.

Services: Services are a set of code that can be shared by different components
of an application. So for example, if you had a data component that picked data
from a database, you …