Big O Flashcards
How can an algorithm be classed as efficient?
-no unnecessary steps
-same outcome but with minimum processing requirements
-shortest execution time
Define Big O notation
A mathematical notation used to describe how well an algorithm will perform as it is given increasingly larger datasets
Define efficiency
The ratio between the work an algorithm produces and its speed or memory requirements.
What do time requirements denote?
The time taken to complete the task
What do space requirements denote?
The amount of memory taken to complete a task
What can the time parameter be based off in a time measure function?
Number of memory accesses, number of comparisons, number of loops etc.
Sometimes refers to the real time taken to execute, run time
What does the parameter of the space measure function depend on?
Whether additional memory is used to store inputs for processing
List the factors that can determine efficiency of an algorithm:
-Human coding time
-time complexity
-space complexity
What factors are used to measure human coding time?
-time taken to develop a program
-time taken to maintain a program
What main factor effects human coding time?
Readability of the program
Define refactoring
Code is restructured without changing its purpose and behaviour to make it more clear, readable and efficient.
Describe the meaning of permutations
The number of ways of arranging objects
What is the formula for calculating the number of permutations?
p = n^r, where n is the number of choices we have, and r is the number of times a choice is made.
Describe the purpose of big O notation
-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
List the types and their notations:
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)
Give an example of an algorithm with a logarithmic time complexity
Binary search
Binary tree search
Give an example of an algorithm with a linear complexity?
Linear search
Describe a constant complexity
An algorithm that executes in the same time no matter the size of a dataset.
Give an example of an algorithm with a polynomial complexity
Bubble sort ( because of nested loop, O(n^2) for one nested loop etc)
Give an example of an algorithm with an exponential complexity
Travelling salesman problem
Permutations calculation
Define tractable problems
Problems that can be solved in a polynomial time or less- solveable in a realistic amount of time
Define intractable problems
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)
Define heuristic algorithms
Provide an approximate, rule of thumb, but not exact solution to algorithms that are not time efficient to solve
