Analysis, Design and Comparison of Algorithms

Question 1

What are two things to check when Analysing an Algorithm

Answer 1

• Time Complexity
• Space Complexity

Question 2

What is the Time Complexity of an Algorithm

Answer 2

How much time an algorthim takes to solve a particular problem relative to the number of inputs it recieves

Question 3

What is Time Complexity measured in

Answer 3

• Big-O notation
• Big-o notation shows the effectiveness of an algorithm
• It shows an upper limit for the amount of time taken relative to the number of data elements given as an input

Question 4

How is Big-O notation written

Answer 4

In the form 0 (n), where n is the : the number of inputted entities, and 0 (n) is the time relationship

Question 5

What are the examples of Big-O Notation

Answer 5

• 0 (k) - Constant Time Complexity - the amount of time taken to complete an algorithm is independent from the number of elements inputted
• 0 (n) - Linear Time Complexity - the amount of time taken to complete an algorithm is directly propoertional to the number of elements inputted
• 0 (n²) - Polynomial Time Complexity (example) - the amount of time taken to complete an algorthim is directly propertional to the sqaure of the elements inputted
• 0 (nⁿ) - Polynomial Time Complexity - the amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n
• 0 (2ⁿ) - Exponential Time Complexity - the amount of time taken to complete an algorithm will double with every additional item
• 0 (log n) - Logarithmic Time Complexity - the time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted increases

Question 6

Give an Algorithm example of each Big-O Notation

Answer 6

• Constant Time - print (“hello”)
• Linear Time Complexity - for ([a,b,c … n] print(“hello”)
• Polynomial Time Complexity - for ([a,b,c … n] for ([a,b,c … n]) print (“hello”)
• Exponential Time Complexity - recursive algorithms with size n
• Logarithmic Time Complexity - a divide and conquer algorithm

Question 7

Describe the Consant Time Complexity Graph

Answer 7

Question 8

Describe the Linear Time Complexity Graph

Answer 8

Question 9

Describe the Polynomial Time Complexity Graph

Answer 9

Question 10

Describe the Exponential Time Complexity Graph

Answer 10

Question 11

Describe the Logarithmic Time Complexity Graph

Answer 11

Question 12

Which are the best and worst time complexities

Answer 12

Question 13

What is the Space Complexity of an Algorithm

Answer 13

The amount of storage the algorithm takes

Question 14

How is Space Complexity written

Answer 14

• Big O notation
• Algorithms store extra data whenever they make a copy, this isn’t ideal
• When working with lots of data it is not a good idea to make copies as they takes up storage which is expensive

Question 15

What is an Algorithm

Answer 15

A series of steps that complete a task

Question 16

When does time complexity take priority and when does space complexity take priority

Answer 16

• If you have a lot of processing power then focus on space complexity
• If you have a lot of data that needs to be processed quickly you would focus on time complexity

Question 17

How do you reduce Space Complexity and Time Complexity

Answer 17

• Reduce Space Complexity - perform all of the changes on the original piece of data
• Reduce Time Complexity - reduce the number of embedded loops, reduce number of items you have to complete operations on (divide and conquer algorithm)

Question 18

What Big-O Notation does the Linear Search Algorithm have

Answer 18

0 (n)

Question 19

What is the Big-O Notation for the Binary Search Algorithm

Answer 19

0 (log(n))

Question 20

What is the Big-O Notation for a Bubble Sort Algorithm

Answer 20

O (n²)