Skip to main content

Featured post

Tennis-Paddle game

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

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 …

What’s the difference between AngularJS, Angular2 and Angular4?

One question that often comes out is “What is the basic difference between AngularJS, Angular 2 and Angular 4 and how to jump from Angular 2 to Angular 4?”


Angular JS was introduced in 2010 as a JavaScript framework for building client side single page web applications. So it gained popularity and the Angular team at google started to add some more features to the core. But the framework was not designed with the needs of today’s applications in mind and moreover it was totally complex. So the Angular team decided to rewrite the entire framework using TYPESCRIPT and as a result Angular 2 was released in mid 2016. The new Angular framework is completely different from the previous version and we can think of it as a completely different framework compared to the earlier one.

The decision was frustrating to most of the developers since a lot of applications have been designed using AngularJS. I personally liked the direction that Angular developers took in rewriting the entire framework a…