Big O

Question 1

How can an algorithm be classed as efficient?

Answer 1

-no unnecessary steps
-same outcome but with minimum processing requirements
-shortest execution time

Question 2

Define Big O notation

Answer 2

A mathematical notation used to describe how well an algorithm will perform as it is given increasingly larger datasets

Question 3

Define efficiency

Answer 3

The ratio between the work an algorithm produces and its speed or memory requirements.

Question 4

What do time requirements denote?

Answer 4

The time taken to complete the task

Question 5

What do space requirements denote?

Answer 5

The amount of memory taken to complete a task

Question 6

What can the time parameter be based off in a time measure function?

Answer 6

Number of memory accesses, number of comparisons, number of loops etc.
Sometimes refers to the real time taken to execute, run time

Question 7

What does the parameter of the space measure function depend on?

Answer 7

Whether additional memory is used to store inputs for processing

Question 8

List the factors that can determine efficiency of an algorithm:

Answer 8

-Human coding time
-time complexity
-space complexity

Question 9

What factors are used to measure human coding time?

Answer 9

-time taken to develop a program
-time taken to maintain a program

Question 10

What main factor effects human coding time?

Answer 10

Readability of the program

Question 11

Define refactoring

Answer 11

Code is restructured without changing its purpose and behaviour to make it more clear, readable and efficient.

Question 12

Describe the meaning of permutations

Answer 12

The number of ways of arranging objects

Question 13

What is the formula for calculating the number of permutations?

Answer 13

p = n^r, where n is the number of choices we have, and r is the number of times a choice is made.

Question 14

Describe the purpose of big O notation

Answer 14

-Big O notation is used to describe how the time requirements of an algorithm grow in relation to the number of items being processed. (worst case scenario)
-n refers to the number of items

Question 15

List the types and their notations:

Answer 15

Constant: O(1)
Linear: O(n)
Logarithmic: O(log n)
Quadratic: O(n^2)
n Log n: O(n log n)
Cubic: O(n^3)
Exponential: O(2^n)

Question 16

Give an example of an algorithm with a logarithmic time complexity

Answer 16

Binary search
Binary tree search

Question 17

Give an example of an algorithm with a linear complexity?

Answer 17

Linear search

Question 18

Describe a constant complexity

Answer 18

An algorithm that executes in the same time no matter the size of a dataset.

Question 19

Give an example of an algorithm with a polynomial complexity

Answer 19

Bubble sort ( because of nested loop, O(n^2) for one nested loop etc)

Question 20

Give an example of an algorithm with an exponential complexity

Answer 20

Travelling salesman problem
Permutations calculation

Question 21

Define tractable problems

Answer 21

Problems that can be solved in a polynomial time or less- solveable in a realistic amount of time

Question 22

Define intractable problems

Answer 22

Theoretically solveable problems, but cannot be solved in a realistic amount of time, take longer than a polynomial time to solve, O(n!) or O(2^n)

Question 23

Define heuristic algorithms

Answer 23

Provide an approximate, rule of thumb, but not exact solution to algorithms that are not time efficient to solve