2.3 Algorithms

2.3 Algorithms


2.3.1 Algorithms

Standards for Writing Algorithms:

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