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
