Paper 2 Module 3 Flashcards
What is the definition of time complexity?
The time complexity of an algorithm is how much time it requires to solve a particular problem.
What are properties of O(1) Big O notation time complexity?
Constant Time Complexity
The amount of time taken to complete an algorithm is independent from the number of elements inputted.
What are properties of O(n) Big O notation time complexity?
Linear time complexity
The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted.
What are properties of O(n^2) Big O notation time complexity?
Polynomial time complexity
The amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted.
What are properties of O(n^n) Big O notation time complexity?
Polynomial Time
The amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n.
What are properties of O(2^n) Big O notation time complexity?
Exponential time complexity
The amount of time taken to complete an algorithm will double with every additional item.
What are properties of O(log n) Big O notation time complexity?
Logarithmic time complexity
The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.
What is the order of time complexities in big(O) notation? Worst to best
O(2^n) and O(n^2)
O(n log(n))
O(n)
O(log(n))
O(1)
What is the definition space complexity?
The space complexity of an algorithm is the amount of storage the algorithm takes.
What is the time complexity for a linear search? and why?
O(n). This is because linear seach algorithm is an algorithm which traverses through every item one at a time until it finds the item it’s searching for.
What is the time complexity of a binary search algorithm?
O(log(n)), a binary search algorithm is a divide and concoer algorithm, this means it splits the list into smaller lists until it finds the item it’s searching for, since the size of the list is halved everytime, its O(log(n)).
what is the time complexity of a bubble sort algorithm?
O(n^2), The bubble sort algorithm passes through the list evaluating pairs of items and ensuring the larger value is above the smaller value. It has a polynomial Big-O notation.
What is a stack?
It is a data structure that is first in, last out. They are often implemented as an array and use a single pointer (top pointer) to manage the data. The top point is initialised at -1 because the first value to enter is at position 0.
What are the operations that you can perform on a stack? and their name?
1.Check size = size()
2. check if empty = isEmpty()
3. Return top element (but don’t
remove ) = peek()
4. Add to the stack = push(element)
5. Remove top element from the stack and return removed element = pop()
what is a queue?
Queues are a type of first in first out data structure. A queue has two pointers the front and the back.
what operations can you do on a queue? and what’s their name?
- Check size = size()
- check if empty = isEmpty()
- Return front element = peek()
4 Add to the queue =
enqueue(element)
5.Remove front element from the
queue and return removed element
= dequeue()
What is a linked list?
A linked list is composed of nodes, each of which has a pointer to the next item in the list. Searching a list is performed using a linear search, carried out by sequential next operations until the desired element is found.
What are trees?
Trees are formed from nodes and edges, which cannot contain cycles and aren’t directed. Trees are useful as a data structure because they can be traversed. You can use depth first and breadth first searches for this.
How do you do a depth first search?
Depth first search goes as far down into the tree as possible before back tracking. The algorithm uses a stack and goes to the left child node of the current node when it can. If there is no left child then the algorithm goes to the right child. If there are no child nodes, the algorithm visits the current node, outputting the value of the node before backtracking to the next node on the stack and moving right.
How do you do a breadth first search?
Starting from the left, breadth-first visits all children of the start node. The algorithm then visits all nodes directly connected to each of those nodes in turn, continuing until every node has been visited. Unlike depth first, breadth first uses a queue.
What is a bubble sort?
It is a sorting algorithm that makes comparisons and swaps between pairs of elements. It starts on the first item and compares it to the second.
What is insertion sort?
It is similar to bubble sort, but it starts on the second item, and comepares it to the item on the left (the first item), a swap stakes place if the second item is larger, if not the program selects the third item. if that is smaller a swap happens and then another comparison is made with the previous values (first value).
what is merge sort?
It is a sorting algorithm that uses divide and conquour technique. The array is split in half until only 2 items remain groups. The items in the groups are compared and reaasembled with an ordered array.
divide and conquer means?
It means taking two or more identical, smaller sub-problems from a larger problem, solving the sub-problems individually and combining their solutions to solve the original, larger problem.
