1.3 algorithms Flashcards
o(n)
the time is takes is directly proportional to the size of the data
o(1)
always takes the same time and the same number of steps (memory) regardless of the amount of data input
o(n^2)
as the number of items steadily increases, the time taken increases more rapidly therefore, the curve gets steeper
o(2^n)
time doubles for each addition to the data set - time is increasing exponentially
o(log2n)
as the number of items steadily increases, the time taken increases by smaller and smaller amounts
o(nlog2n)
divide and conquer
the graph is like a massive quadratic with less of a curve
explain the purpose of procedures (sub-routines)
- algorithms/programs can be broken down into smaller parts
- these are names reusable pieces of code that can be called any number of times within an algorithm/ program to perform a specific task
- procedures are used to avoid the duplication of code
- each procedures can be individually tested/ debugged
- procedures are used to make an algorithm/program more efficient and secure (try not to use this point)
the difference between local and global variables
what is meant by passing by reference and why is it used
- where a address is passed via a parameter into a subroutine and the original value is passed and used by that subroutine
- this is used if any changes made in the subroutine needs to be stored in the original value/variable outside the subroutine
what is meant by passing by value and why is it used
- where a value is passed via a parameter into a subroutine and a copy of the value is created for the duration of the subroutine cell
- this ensures that the original value passed to the subroutine cannot be changed
why is self documenting identifiers important and give an example
- allows code to be followed and understood more easily
- reduces the need for the additional documentation to be produced, such as additional annotation or software manuals
- example: VAT or firstname
why is program layout important and give an example
- allows blocks of code and constructs to be followed and identified more easily
- a consistent program layout helps improve the quality of the software and allows developers to maintain quality and standards
-example: indentation to identify the start and end of constructs such as IF statements, Loop/nested loop structures
why is annotation is important and give an example
- allows developers to record the development process and logic with the actual code
- many developers could be working on the one project and each developer needs to understand the logic between one and others code
-example: X DIV 2 ‘calculates if X is even or odd
why is it good programming practice to use constants, meaningful names for variables and annotation in computer programs
- they can be set once and then used many times throughout the program and if they change then they only have to be changed once. (constants)
-it is clear what the variable is holding and aids program readability (meaningful names)
-other programmers will find the code easier to follow (annotation)
benefit of passing by value
- avoids problem of unintended side affects where the parameter has its value changed in the main program as well as in the procedure
benefit of passing by reference
- avoids the larger amount of processing/storage (associated with passing by value, possibly large amounts of copying)
-allows change to be passed back to the calling program
what is the purpose of validation and give an example
- is the process of checking if the data entered is sensible in the context in which it is being used
-reduces the possibility of entering invalid data into a system
example:
range checks on dates
2 situations where a linear search will generally perform faster than a binary search
- when the number of items to be searched is very small
- the search value is one of the first items in the array
1 situation where a binary search will generally perform faster than a linear search
- when there is a large sorted data set
