Unit 8- Algorithms Flashcards
What does Big O Notation measure?
Time Complexity
What is the time complexity of an algorithm with two nested loops?
O(n^2)
What is the big O notation for the most efficient algorithms and why is this often unrealistic?
O(1), if the algorithm inputs numbers, it is hard to make an algorithm which isn’t affected by the size of the number, however this isn’t never, accessing data in an array for example doesn’t matter how large the number is (as long as its in the array it will take the same amount of time to access)
If two algorithms have the same big O notation, do they take the same amount of time to run?
No, for example an algorithm that takes 2n seconds to run, has the same big O notation as one that takes 3n+16.
What is recursion?
Recursion is when a subroutine calls itself from within the subroutine.
What must recursive subroutines contain?
They must have a stopping condition (or a base case) which will make it unwind so that it does not go on forever. It must stop after a finite number of calls.
What three things do call stacks hold?
Return adresses, parameters, and local variables.
Types of tree traversals:
In-order, pre-order, post order.
Step of Djkstras Algorithm
- Create a queue of all starting nodes with the starting node at the front and add to each their distance from starting node.
- Remove the front node and add to the visited list
- Update the distances of each node connected to the visisted node
- Reorginise the queue so that the nodes are ordered in terms of their distance (shortest first)
- Repeat the steps above until all nodes have been visisted(moved to the front and dropped down to the visisted list)
- You will be left with a lists of nodes and there shortest distance from there starting nodes.
What is a tractable problem?
A problem that has a polynomial time complexity or better,
What is a computable problem?
Computatble problems are problems that can be solved by an algorithm that can be solved in a finite number of steps
