ScaleFree

DS & A (Algorithm Analysis - Faster Computer OR Faster Algorithm)

By

| CHAPTER 6 |

Till now we have been talking about various concepts in Data Structures & Algorithms but in this chapter, we will be focusing more on a question rather than some concept. So, let's get started.

Since we are already familiar with the basics of algorithms and it's running time, I would like to ask you guys a question, what contributes more to reducing the running speed of a program? 
  • A faster computer?
  • Or a faster algorithm?
Pick One: Faster Algorithm or Faster Computer

Before you guys come to an answer, I would like to remind you guys that how fast a program runs depends on the running time of an algorithm and the machine it is running on as well. I know you guys will try to think out of the box and ask why not both? But in this chapter, we will be focusing more on picking the better choice out of the two given options. 

Now, before picking our answer let us analyze both the available options. Suppose, there are two algorithms for a single problem, algorithm A, and algorithm B, with running time n and n2 respectively. An old computer is able to run algorithm A in X amount of time. But running algorithm B in the old computer takes 10 times more time than running algorithm A, i.e. 10X amount of time. Now, if we replace the old computer with a new one that is 10 times faster, will the new computer be able to run algorithm B 10 times faster, i.e. in (10X/10 = X) amount of time, compared to the old computer? If the size of our problem remains the same then the new computer will definitely run algorithm B faster but if it's by 10 times or not completely depends on the running time of the algorithm. And even if the new computer somehow, does run the algorithm B 10 times faster, i.e. in X amount of time, compared to the old computer it is just solving a bigger problem as the old computer can finish the same problem with algorithm A in X amount of time.

For algorithm A [T(n) = n]

Suppose, the old computer runs 1,000 operations in X amount of time. So, we will definitely expect our new computer to run 10,000 operations in X amount of time as it is 10 times faster. If we run algorithm A, then, definitely the new computer will run 10 times more operations compared to the old computer in the same amount of time, but that is only true for algorithm A as it is of linear runtime. 

The Old Computer runs 1,000 operations in X amount of time. Since the running time of the algorithm is n which means for every operation the computer needs n amount of time. So, 1,000 operations needs 1,000n time or X = 1,000n. Similarly, In 1,000n time the new computer can run 10,000 operations.

The above statements can also be written as,
  • In 1,000n time the old computer can run 1,000 operations or In n time the old computer can run 1 operation.
  • Also in 1,000n time, the new computer can run 10,000 operations or In n time the new computer can run 10 operations
So, the new computer runs 10 times more operation in n time for algorithm A.

For algorithm B [T(n) = n2]

In case of algorithm B, it is not that simple. Since algorithm B is of  n2 running time we cannot directly say the number of operations that run on each computer in X amount of time. 

Let's assume that the old computer runs 100 operations in time X for algorithm B. Since the running time of the algorithm is n2, that means for every operation the computer needs n² amount of time. So, 100 operations need 100n2  time or X = 100n2 . Similarly, In 1,00n2 time the new computer can run 1,000 operations.

The above statements can also be written as,
  • In 100n2 time the old computer can run 100 operations or In n2 time the old computer can run 1 operation. Therefore, in n time the old computer can run √1 operations.
  • Also in 100n2 time, the new computer can run 1,000 operations or In n2 time the new computer can run 10 operations.  Therefore, in n time the old computer can run  √10 operations.
So, the new computer runs √10 times more operations in n time for algorithm B.

So, we can clearly see that a 10 times faster computer doesn't always ensure 10 times faster processing.

Algorithms with other Growth rates...


 f(n)

 n

 n’

 change

 n’/n

 10n

 1,000

 10,000

 n’ =10n

 10

 5n log(n)

 250

 1842

 √10n < n’ <10n

 7.37

 2n2

 70

 223

 n’ = √10n

 3.16
f(n)       = Growth rate equations
n          = Maximum number of operations that can be run on the old machine in time T
n'          = Maximum number of operations that can be run on the new machine in time T
change = Number of times by which the new computer can run the given growth rate 
                algorithm faster compared to the old computer
n'/n       = Ratio of increase in problem Size

So, we can see from the table above as well that getting a faster computer is not a better solution so we should always try to ensure the fastest possible algorithm before looking for a faster computer. Furthermore, if we do buy a faster computer, ensuring a faster algorithm just makes it a better deal as it allows us to run the algorithm work on larger problems efficiently.
( If you like the content here, follow TSP on social media to get notified on future updates)


Comments

Post a Comment

Share on Social Media

Most Viewed Posts

DS & A (Algorithm Analysis - Best, Worst and Average Case)

By
Image
|  CHAPTER 5  | Note: If it's your first time visiting this website I strongly recommend you to read the previous chapter before reading this chapter. Till now we learned about what Data Structures and Algorithms are, some basic terminologies and a few  concepts  of Algorithm analysis.   And continuing our ongoing journey of Data Structures and Algorithms, today we will discuss the Best Case, Average Case and Worst Case of an algorithm. Algorithm Case Analysis In the last chapter, we learned that every algorithm has running time[T(n)] and a growth rate. But that's not the end of it, an algorithm's running time and growth rate are not the only factors that we should consider while designing an algorithm. For some algorithms, different inputs result in different running time. And that brings forth the necessity of the concept of Best, Average, and Worst Case of algorithms. Example Consider we have four boxes tagged 1,2,3 & 4, and the boxes con
Read more

SPACE & DRAGONS

By
Image
Space and Dragons is a top-down endless space shooter where the player takes on the role of a brave space warrior. In the game, the player has to fight against fierce Space Dragons while making the way through other obstacles such as space debris and much more. FEATURES: SPACE DRAGONS MOVING DEBRIS POWER-UPS HEALTH BOOST SHIELD AND much more SCREENSHOTS...... APPLICATIONS USED : QT Creator (A C++ based framework) GIMP (An Image Manipulation Software) AUDACITY (An Audio Manipulation Software) NOTE: The game resources have been collected from the OpenGameArt website and various other online sources. The used game assets are not my property. GAME DOWNLOAD LINK: DOWNLOAD GAME GAME REQUIREMENTS OS : WINDOWS RAM : 1 GB HARD DRIVE : 150 MB CONTROLS: LEFT, RIGHT keys for movements and SPACE to Shoot SPACE SHOOTER IN ACTION UPDATE << Click here to download the source code >> Zip Password: TheSuperProgrammer NOTE: The game
Read more

DS & A(Queue)

By
Image
|  CHAPTER 14  | In this chapter, our topic of discussion will be the "Queue" Data Structure. But, before we get started, I would recommend you to read the previous chapters on Data Structures & Algorithms  (especially the chapters on Array List , Linked List , Array Stack , and Linked Stack ), that is in case it's your first time visiting my blog. Queue: Just like Stacks, Queues also are a restricted version of List but with a few minor differences compared to Stack. The following are some of the notable characteristics of a Queue: Data can only be inserted from the rear/back. Data insertion is referred to as  ENQUEUE . Data can only be deleted from the front. Data deletion is referred to as  DEQUEUE . Alternatively,  ENQUEUE  and  DEQUEUE  should always be executed on the opposite ends of the Queue. A Queue follows the  FIFO (First In First Out)   principle. The first and the last elements are referred to as FRONT and REAR respectively.
Read more