Why study Algorithms and performance ?
algorithms that is independent of:
One of the most important aspects of an algorithm is how fast it is. It is often easy to come up with an algorithm to solve a problem, but if the algorithm is too slow, it’s back to the drawing board. Since the exact speed of an algorithm depends on where the algorithm is run, as well as the exact details of its implementation, computer scientists typically talk about the run time relative to the size of the input.
For example: If the input consists of N integers, an algorithm might have a run time proportional to N2, represented as O(N2). This means that if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2 seconds, where C is some constant that doesn’t change with the size of the input.
- Algorithms help us to understand scalability.
- Performance often draws the line between what is feasible and what is impossible.
- Algorithmic mathematics provides a language for talking about program behavior.
- Performance is the currency of computing.
- The lessons of program performance generalize to other computing resources.
- Speed is fun!
- Simple recursive algorithms.
- Backtracking algorithms.
- Divide and conquer algorithms.
- Dynamic programming algorithms.
- Greedy algorithms.
- Branch and bound algorithms.
- Brute force algorithms.
- Randomized algorithms.
- Algorithms that use a similar problem-solving approach can be grouped together .
- This classification scheme is neither exhaustive nor disjoint .
- The purpose is not to be able to classify an algorithm as one type or another, but to highlight the various ways in which a problem can be attacked .
algorithms that is independent of:
- Machine, processor, architecture
- Size of data sets, ordering of data
- Computer language
- Compiler used
One of the most important aspects of an algorithm is how fast it is. It is often easy to come up with an algorithm to solve a problem, but if the algorithm is too slow, it’s back to the drawing board. Since the exact speed of an algorithm depends on where the algorithm is run, as well as the exact details of its implementation, computer scientists typically talk about the run time relative to the size of the input.
For example: If the input consists of N integers, an algorithm might have a run time proportional to N2, represented as O(N2). This means that if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2 seconds, where C is some constant that doesn’t change with the size of the input.
Approximate completion time for algorithms, N = 100
| O(Log(N)) | 10-7 seconds |
| O(N) | 10-6 seconds |
| O(N*Log(N)) | 10-5 seconds |
| O(N2) | 10-4 seconds |
| O(N6) | 3 minutes |
| O(2N) | 1014 years. |
| O(N!) | 10142 years. |
What is the big O notation?
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O
specifically describes the worst-case scenario, and can be used to
describe the execution time required or the space used (e.g. in memory
or on disk) by an algorithm.
What is the time complexity?
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input:226. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms.
