# Unit 12 Algorthiums Flashcards

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 time complexity of an algorithm is how much time it requires to solve a particular problem. The time complexity is measured using a notation called big-o notation, which shows the effectiveness of the algorithm. It shows an upper limit for the amount of time taken relative to the number of data elements given as an input. This is good because it allows you to predict the amount of time it takes for an algorithm to finish given the number of data elements.

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?

The amount of time taken to complete an algorithm is independent from the number of elements inputted. O(n)

What does a constant time complexity mean?

The amount of time taken to complete an algorithm is independent to the number of inputted elements. O(1)

What does a polynomial time complexity mean?

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n. O(n2)

What does an exponential time complexity mean?

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted. O(2N)

What does a logarithmic time complexity mean?

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted. O(Log n)

What is a logarithm?

How many times a certain number (base) is multiplied together to reach another number.

What is space complexity?

The space complexity of an algorithm is the amount of storage the algorithm takes. Space complexity is commonly expressed using Big O (O(n)) notation. Algorithms store extra data whenever they make a copy, this isn’t ideal. When working with lots of data, it’s not a good idea to make copies. As this will take lots of storage which is expensive.

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 is the Big-O notation of a linear search algorithm?

O(n)

Function linearSearch(list, item)

index = -1

i= 0

found = False

while i < length(list) and found = False

if list[i] = item then

index = i

found = True

endif

i=i+ 1

endwhile

return index

endfunction

What is the Big-O notation of a binary search algorithm?

O(log(n))

function binarySearch(list, item)

found = False

index = -1

first = 0

last = length(list) - 1

while first <= last and found = False

midpoint = int ( first + last) / 2 )

if list[midpoint] = item then

found = True

index = midpoint

else

if list[midpoint] < item then

first = midpoint + 1

else

last = midpoint - 1

endif endif

endwhile

return index

endfunction

What is the Big-O notation of a bubble sort algorithm?

O(n2)

function bubbleSort(list, item)

found = False

i= 0

while found = False and i < length(item)

if list[i] > list[i+1]

temp = list[i]

list[i] = list[i+1]

list[i+1] = temp

endif

i = i +1

endwhile

return list

endfunction

Stacks

Stacks are an example of a first in, last out (FILO) data structure. They are often implemented as an array and use a single pointer which keeps track of the top of the stack (called the top pointer). This points to the element which is currently at the top of the stack.

The top pointer is initialised at -1; this is because the first element in the stack is in position 0, and having the top initialised at 0 would suggest there is an element in the stack, when in fact the stack is empty.

Algorithms for stacks include adding to the stack, removing from the stack and checking whether the stack is empty/full. These have their own special names, as shown in the table below.