2.3 - Algorithms
No description yet. This curated deck is ready for daily study.
Card preview (24)
What two pieces of information allow you to analyse an algorithm?
● Time Complexity ● Space Complexity
What is meant by the time complexity of an algorithm?
The amount of time required to solve a particular problem
How do you measure of the time complexity?
Big-O notation
What does the big-O notation show?
The effectiveness of an algorithm
What is the Big-O notation good for?
It allows you to predict the amount of time taken to solve an algorithm given the number of items stored
What does a linear time complexity mean?
O(n) This is where the time taken for an algorithm increases proportionally or at the same rate with the size of the data set. For example, finding the largest number in a list. If the list size doubles, the time taken doubles.
What does a constant time complexity mean?
O(1) This is where the time taken for an algorithm stays the same regardless of the size of the data set. For example, printing the first letter of a string. No matter how big the string gets it won’t take longer to display the first letter.
What does a polynomial time complexity mean?
O(n^k) (where k>=0) This is where the time taken for an algorithm increases proportionally to n to the power of a constant. Bubble sort is an example of such an algorithm.
What is space complexity?
The space complexity is the amount of storage space an algorithm takes up
What is an algorithm?
An algorithm is a series of steps that complete a task
How do you reduce the space complexity?
Try to complete all of the operations on the same data set
How do you reduce the time complexity of an algorithm?
You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer
What does a Logarithmic time complexity mean?
O(log n) This is where the time taken for an algorithm increases logarithmically as the data set increases. As n increases, the time taken increases at a slower rate, e.g. Binary search. The inverse of exponential growth. Scales up well as does not increase significantly with the number of data items.
What is the Big-O notation of a linear search algorithm?
O(n)
What is the Big-O notation of a binary search algorithm?
O(log(n))
What is the Big-O notation of a bubble sort algorithm?
O(n^2)
Are stacks FIFO or FILO?
FILO
What is the significance of the back pointer in the array representation of a queue?
Holds the location of the next available space in the queue
What is the purpose of the front pointer in the array representation of a queue?
Points to the space containing the first item in the queue
What value is the top pointer initialised to in the array representation of a stack?
-1
Give pseudocode for the two functions which add new elements to stacks and queues
STACK push(element) top += 1 A[top] = element QUEUE enqueue(element) A[back] = element back += 1
Give pseudocode to push onto a stack
PROCEDURE AddToStack (item): IF top == max THEN stackFull = True ELSE top = top + 1 stack[top] = item ENDIF ENDPROCEDURE
Give pseudocode to pop onto a stack
PROCEDURE DeleteFromStack (item): IF top == min THEN stackEmpty = True ELSE stack[top] = item top = top - 1 ENDIF ENDPROCEDURE
Give pseudocode to enqueue onto a queue
PROCEDURE AddToQueue (item): IF ((front - rear) + 1) == max THEN queueFull = True ELSE rear = rear - 1 queue[rear] = item ENDIF ENDPROCEDURE