Algorithms and Programming Flashcards
Define Recursive Algorithm
An algorithm that recalls itself during its run time
Describe the recursion method
It is a method of solving a problem where the solution depends on solving increasingly smaller instances of the same problem
How is a stack overflow caused
When a recursive algorithm has no base case to stop itself.
What is the Base Case
It sets the very end of where the algorithm can run to, as it will then force it to end
What is the general case
A section of the program that decreases in size each time the algorithm is called
What does Big O notation find
The complexity of an algorithm
How are algorithms compared
In terms of their complexity
What are the two versions of an algorithm Big O notation looks at
The longest version
The shortest version, Which is called the constant complexity
What does O(1) represent
The constant complexity, the shorts time any algorithm can take
What is the best outcome of an algorithm
Constant complexity
what does O(n) represent
A linear time where the time taken is directly proportional to the size of n
What does O(n^2) represent
The polynomial complexity, since the greater the amount of data the greater the time complexity
what does O(2^n) represent
The exponential complexity, since the result is doubled each time n increases by 1
Which is worse O(n^2) or O(2^n)
O(2^n)
What version of the Big O notation do we use to estimate the run time in a worst case scenario
The largest version, since the smaller parts can be seen as inconsequential to the larger parts
Define Best case
The algorithm only have to run once
Define Worst case
the algoroithm needs to run the greatest possible number of times
Define Average case
The algorithm has to run for a reasonable length of time
How do we compare two different algorithms
We compare their graphs and see at an amount of data which will take longer to complete
Define an algorithm
A step by step set of instructions which provides a solution to a specific problem
Explain Binary search algorithms in short
Search the middle of a sorted array, if the middle item is higher or lower than the item you are looking for you search the middle of the corresponding half and so on until you find the value
Explain Bubble sort algorithms in short
Starting from the left, you compare each item and swap them if the one on the left is greater than the right one, this repeats throughout the entire array and then repeats again until no swaps are made
