Algorithms Flashcards
What is meant by time complexity of an algorithm?
How much time it takes to solve a particular problem inputted
Constant time complexity
O(1) Time taken is independent of the number of elements inputed
Linear time complexity
O(n) Time take is directly proportional to the number of elements inputted
Polynomial time complexity
O(n^n) Time taken is directly proportonal to the number of elements to the power of n
Exponential time complexity
O(2^n) Time taken will double as the input size increases by one
Logarithmic time complexity
O(log n ) Time taken will increase at a smaller rate than the number of elements inputted
Best to worst time complexities for an algorithm
best
o(1)
o(logn)
o(n)
o(nlogn)
o(n^2)
o(2^n)
What is meant by the space complexity of an algorithm?
The amount of storage an algorithm takes
What is the time complexity of linear search?
O(n) linear
What is the time complexity for binary search?
O(log n) logarithmic
Because the size of the list is halved every step
Give an example of a divide and conquer algorithm?
What does this mean for an algorithm?
Binary search or merge sort
Binary: Splits the list into half
Conquer: It recursively/ iteratively searches in one of the halves based on a comparison (whether the target is less than, greater than, or equal to the middle element).
Combine: In the case of binary search, there’s no explicit “combine” step, but the result of each list division which eventually leads to the target or that it’s not present.
Mergesort:
Divide: Split lists in half until each contains just one element
Conquering each subproblem recursively (ordering).
Combining the results of the subproblems to get the final solution.
What is the time complexity of merge sort?
O(nlogn)
What would the top pointer of a stack be initialised to?
Why?
-1 because the first element in the stack is in possition 0. Having the pointer initialised at 0 would suggest there is already an element in the stack even though the stack is empty
(item is inserted into pointer+1 index)
Pseudocode for function which returns number of elements on a stack
size()
return top +1
Pseudocode for function which returns number of elements on a queue
size()
return back - front
What is a linked list?
-A data structure composed of nodes, each of which has a pointer to the next node in the sequence.
(Unlike arrays, linked lists do not store elements in contiguous memory locations)
each node contains two parts:
Data: The value or data that the node holds.
Next (or Pointer/Link): A reference/pointer to the next node in the list. If it’s the last node, this pointer is null
-First item in a list is called the head and the last is the tail
E.g if a node is called N then the next node is referred to as N.next
Define tree
A tree is a connected, undirected graph that contains no cycles
What is the time complexity for the bubble sort algorithm?
O(n^2)
Depth first traversal
Go as far down into the tree as possible before backtracking
by Goes to the left child node of the current node
If there is no left child print node then go to right child and output
If there are no child nodes, visit current node and output value then backtrack to the next node on stack and moving right output
Uses a stack
(like postorder traversal)
Breath first traversal
Starting from left, visits all children of start node
If one has to children then backtracks
Uses a queue
Breath first traversal uses a stack
TRUE OR FALSE?
FALSE
Uses a queue
What data structure does depth first traversal use>?
Stack
What is the time complexity of insertion sort?
O(n^2)
What is the time complexity of merge sort?
O(nlogn)
Bubble sort is more efficient than insertion sort and merge sort
TRUE OR FALSE
FALSE
Merge sort is more efficient than bubble sort and insertion sort
Merge O(nlogn)
Insertion and bubble O(n^2)
What is the time complexity of quick sort?
O(n^2)
Binary search can be applied on sorted and unsorted data
TRUE OR FALSE?
FALSE
Only applied on sorted data
The time complexity of binary search is O(n^2)
TRUE OR FALSE?
FALSE
O(logn)
What is the time complexity of linear search?
O(n)
The A* algorithm has 2 cost functions
What are they?
- Actual cost between two nodes (same as in Dijkstras)
- Approximate cost from node x to the final node (called a heuristic)(might be the estimate length between x and the final node, calc using trig)
