Sorting Algorithms and Big O notation

Question 1

Big O notation

Answer 1

This is a special notation for classifying algorithms based on how their computational times grows as their input size grows

Question 2

Time Complexity

Answer 2

How much time they need to solve a given problem

Question 3

Space Complexity

Answer 3

The amount of resource e.g. memory they require

Question 4

Factorial

Answer 4

The permutation of a set of objects simply means the number of ways you can arrange those objects

Question 5

Function maps one set of values to another

Answer 5

Nothing more than mapping of one set of inputs onto a set of outputs, one element of the input set always relates to one element of the output

Question 6

Key terms for Function

Answer 6

• Domain: All the possible inputs of a function f
• Range: Set of all outputs of f
• Codomain: All the possible values that may be output from a function f

Question 7

Serial Array big o notation

Answer 7

Adding items to a serial array and a list is constant time complexity - O(1)

Question 8

Linear Search

Answer 8

Linear time complexity is O(n) at worst case scenario and if directly to an element of an array O(1)

Question 9

Sequential array

Answer 9

adding items to a sequential array is time complexity O(n)

Question 10

Sorted array

Answer 10

uses binary search, halves the set of numbers with each selection, therefore is time complexity O(log n)

Question 11

Stack or Queue

Answer 11

Pushing and popping from stacks or queues O(1), searching through a stack / queue is O(n)

Question 12

Hashing

Answer 12

Hashing is 0(1) to insert and find assuming item isn’t a synonym otherwise it is O(n) to find an item in the overflow, constant time complexity is much better

Question 13

Linked List

Answer 13

Searching in a linked list is O(n), inserting/ deleting items from a linked list is O(1)

Question 14

Binary tree insertion

Answer 14

binary tree insertion and searching is O(log n). Traversal is O(n)

Question 15

Bubble and Insertion sort, and quick sort

Answer 15

They use a nested loop and they use O(n^2)

Question 16

Quick tips for exams if you see these you can assume it is the big o notation on the other side - No loop, for while loop, nested loop, halving a data set, recursive

Answer 16

No loop = O(1)
For/While loop = O(n)
Nested Loop = polynomial: O(n^number of loops)
Halving a data set = logarithmic: O(log n)
Recursive = exponential: O(2^n)