The algorithms section of the course can be considered the hardest, in this document there are explanations, summaries and examples of the different algorithms and will cover:
Analyzing Algorithms
Time Complexity
Logarithms
Space Complexity
Searching Algorithms
Sorting Algorithms
Path-Findin...
Analysis, Design and Comparison of Algorithms:
Analysis of algorithms:
When developing an algorithm, there are 2 different things to check:
Time complexity
Space complexity
Time complexity:
The time complexity of an algorithm is how much time it requires to solve a particular problem. The time
complexity is measured using a notation called big-o notation, which shows the effectiveness of the
algorithm. It shows an upper limit for the amount of time taken relative to the number of data elements
given as an input. This is good, because it allows you to predict the amount of time it takes for an
algorithm to finish given the number of data elements.
You can think of this as a graph, as the number of data elements entered against the time taken to
complete the algorithm. This will be helpful for showing the relationships between time and the number
of elements inputted. These are shown below.
Big-O notation is written in the form O(n), where n is the relationship between n: the number of
inputted entities, and O(n) is the time relationship. Below are examples of different big-O notations:
Big-O notation Name Description
O(1) Constant time complexity The amount of time taken to complete an algorithm
is independent from the number of elements
inputted.
O(n) Linear time complexity The amount of time taken to complete an algorithm
is directly proportional to the number of elements
inputted.
O(n2) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the square of the number
of elements inputted.
O(nn) Polynomial time complexity The amount of time taken to complete an algorithm
is directly proportional to the elements inputted to
the power of n.
O(2n) Exponential time complexity The amount of time taken to complete an algorithm
will double with every additional item.
O(log n) Logarithmic time complexity The amount of time taken to complete an algorithm
will increase at a smaller rate as the number of
elements inputted.
When calculating the time complexity, you should think logically through the algorithms. Below are a
few examples:
Algorithm example Big-O notation
This example is unrelated to the number of items Constant time:
inputted: This will always take the same amount of time to
For example: complete regardless of the number of values
Print(“hello”) inputted.
, This example is directly proportional to the Linear Time Complexity:
number of items inputted: The time taken to complete the algorithm is
For example: related to the number of items inputted.
inuttedValue = [a,b,c,…,n]
for I in range(len(inputtedValue)): The number of operations completed was
print(“hello”) proportional to the inputted value.
This example is proportional to the number of Polynomial Time Complexity:
items inputted: The amount of time taken to complete the
For example: algorithm is proportional to the number of items
inputtedValue[a,b,c…n] inputted to the power of n.
for I in range(len(inputtedValue)):
for I in range(len(inputtedValue)): The power given to the polynomial is the same as
print(“hello”) the number of embedded loops.
This example is exponentially proportional to the Exponential Time Complexity:
number of items inputted: The amount of time taken to complete the
For example: algorithm is proportional to 2 to the power of the
Recursive algorithms that solve a problem of size number of items inputted.
N by recursively solving 2 smaller problems f size
N-1 This is common with recursive algorithms solving
2 smaller problems of size n-1
This example is logarithmically related to the Logarithmic time complexity
number of items inputted:
for example:
a divide and conquer algorithm is a good example
of this, the number of items you have to search
through gets halved each time.
Time Complexity Graphs:
Constant Time Complexity:
, Linear Time Complexity:
Polynomial Time Complexity:
Exponential Time Complexity:
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 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 michaellawther. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £7.49. You're not tied to anything after your purchase.
