Notes and Key Points on Algorithms, Time Complexity and the Limits of Computation
14 views 0 purchase
Course
Unit 3 - Fundamentals of algorithms
Institution
AQA
These are some of my notes for the AQA A-Level Computer Science course on algorithms, time and space complexity, the classification of algorithms, computational limits, and a few other small areas.
The document includes a range of formatted equations, worked examples of Dijkstra's algorithm with...
Classification of Algorithms
#computer-science #algorithms #classification-of-algorithms
Algorithm Definition
A set of instructions required to complete a given task.
For any given problem, there will be multiple algorithms (for example,
Dijkstra's Shortest Path Algorithm is one shortest path algorithm).
Ideally, you want to use the most efficient algorithm -- i.e. the one which
runs quickly and uses minimal resources.
Time Complexity
How long does the algorithm take to run compared to other algorithms.
Space Complexity
How much memory is required compared with other algorithms.
The key factor is called the input size or the problem size . Typically, this
is the number of data items/nodes/etc.
Algorithm Efficiency Based on Problem Size
Some algorithms are effective for small data sets, but inefficient for
large ones.
Short Overview of Mathematical Functions
, Key Functions:
Constant functions 49
Linear functions 2x
Polynomial functions 2x 2
Exponential functions 2 x
Logarithmic functions log 10
x
Definition of a Permutation
A permutation is the number of ways a set of n items can be arranged.
In the trivial case, this is n!
Big O Notation
Describes the time complexity of an algorithm in the worse-case
scenario [1] as the input time increases.
For example, the bubble sort becomes rapidly unusable, while the
mergesort continues to work in a reasonable amount of time.
Big O calculates the maximum time for an algorithm to complete given n
data items.
Five Main Big O Notations
Constant Time O(1): The algorithm takes the same amount of time
however big the input size is
Logarithmic Time O(log n): The algorithm scales with log n
Linear Time O(n): Time is directly proportional to the size of the
data
Polynomial Time O(n 2
)
Exponential Time O(2 n
)
Disambiguation
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pencilcaseman. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.45. You're not tied to anything after your purchase.
