ScaleFree

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

Faster Computer OR Faster Algorithm - 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 nrespectively. 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 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

Share on Social Media

Most Viewed Posts

DS & A (Lists - Array Based)

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS