This is the topic: 2.3 Algorithms for the OCR Computer Science (H446) course. I got 4 A*s in my A-Levels (Computer Science, Physics, Maths, Further Maths) , so they are very detailed and cover all of the specification for this topic.
Companies may enforce standard rules about writing functions:
No function should be longer than a single page of code. This reduces complexity and aids
readability.
Variable identifiers must conform to a standard convention. This helps others to understand
the code and decreases the likelihood of duplication, making maintenance easier.
Each function should have a single-entry point. This reduces complexity and makes the
search for any bugs more straightforward.
Variables shouldn’t be set up outside the scope of a function. This sets a limit on where to
look for bugs and reduces the likelihood of a problem spread across many modules.
Comments aid readability and allow people to collaborate on code.
Big O Notation:
Algorithms have a time and space complexity. These are independent of the hardware and CPU used
to run the algorithm.
Time Complexity = The execution time in terms of operations performed.
Space Complexity = How much memory an algorithm requires to complete.
Big O Notation is used to express the complexity of an algorithm. It measures the number of steps
and memory usage change according to the data as the amount of data being processed increases.
Big O Notation Name What it Means
O(1) Constant The time/memory used does not change. It is independent
from the amount of data being processed.
O(n) Linear The time/memory used is proportional to the amount of data
being processed.
O(n2) Polynomial The time/memory used is proportional to the number of
elements to the power of k. In this case (quadratic), the
time/memory used is proportional to the square of the
amount of data being processed.
O(log(n)) Logarithmic The time/memory used increases at a smaller rate as the
amount of data increases.
O(nlog(n)) Linearithmic (Don’t need to know what it means)
O(2n) Exponential The time/memory increases by kn with every item. In this
case, the time/memory doubles with every additional item.
Best
Worst
1
, Searching Algorithms:
Linear Search:
The items don’t have to be sorted.
1. Starting at the first element, it sequentially
compares each element to the target item.
2. It stops when it finds the target item and sets the
found flag to true…
3. …or it reaches the end of the list.
Worst Time Best Time Space
O(n) O(1) O(1)
Pros:
Simple to implement
Doesn’t have to be sorted
Cons:
Can be inefficient, especially for long lists.
Binary Search:
The items have to be ordered. It is a divide and conquer algorithm.
1. It calculates the midpoint position of the list by adding the
upper bound to the lower bound, dividing by 2 then rounding.
2. It goes to the midpoint item and compares it to the target
item.
3. If the midpoint is equal to the target item, a found flag is set to
True and the item (or flag) is returned.
4. If the midpoint is less than the target, the upper half of the list
becomes the list to search. The lower bound becomes the
midpoint + 1.
5. If the midpoint is greater than the target, the lower half of the
list becomes the list to search. The upper bound becomes the
midpoint – 1.
6. It repeats this until the item is found, or…
7. If the lower bound is greater than or equal to the upper bound,
the target is not in the list.
Worst Time Best Time Space
O(logn) O(1) O(1)
Pros:
It’s very efficient
Cons:
The list must be sorted
2
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 maddysunter1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.13. You're not tied to anything after your purchase.
