Join TSR
 
 About Us | FAQs | Sign in
 
HomeForumsArticlesRevision NotesPersonal StatementsUniversity GuidesHealth & RelationshipsPostgraduate StudyCareersFreshers
Join the UK's largest student community  
Advanced
Search

Join The Student Room Today

Be part of the UK's largest and fastest growing student community.

It's free to join and a lot of fun - Get inspired, express your ideas, interact and share

Join The Student Room Today

Revision:Algorithms

From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Algorithms


An algorithm is defined as a finite sequence of unambiguous instructions for solving a problem.

  • Every algorithm requires an input
  • The output depends only on the input
  • The algorithm must terminate in a finite time for all inputs (it doesn't get stuck in a loop)

Contents

Order

The order of an algorithm is a measure of the approximate run time for an algorithm, depending on the size of the problem. For large problems we only need to consider the dominant term to get an approximate run time.

The efficiency of an algorithm is a measure of how well an algorithm copes with an increase in the size, n, of a problem. The efficiency decreases as run time increases.

Order Run time proportional to
Linear n
Quadratic n^2
Cubic n^3
Exponential x^n or n!

Example

A computer takes 2 seconds to solve a problem of size 30. Estimate the times taken to solve a problem of size 300 if the algorithm used has

  • an order n

2 \times \frac{300}{30} = 20\ seconds

  • an order n2

2 \times (\frac{300}{30})^2 = 200\ seconds \approx 3.33\ minutes

  • an order n3

2 \times (\frac{300}{30})^3 = 2000\ seconds \approx 33.3\ minutes

  • an order 2n

time \propto 2^n t = k \times 2^n 2 = k \times 2^{30}

k = \frac{2}{2^{30}}

Therefore, using n = 300

t = 2^{300} \times \frac{2}{2^{30}} t \approx 3.79e81\ seconds \approx 1.2e71\ millenia

Also See

See the other D1 notes:

  1. Algorithms
  2. Sorting algorithms
  3. Packing algorithms
  4. Graphs and networks
  5. Minimum connector problems
  6. The shortest path
  7. Route inspection
  8. The travelling salesman problem
  9. Linear programming
  10. The simplex algorithm

Comments

Retrieved from "http://thestudentroom.co.uk/wiki/Revision:Algorithms"
Article Tools:  Create New Article  |  Report This Article  |  This Article's History  |