Computer Science

O(n²) complexity type

Polynomial

O(n) complexity type

Linear

Asymmetric encryption

Public key - encrypts data
Recipient’s private key - decrypts data

One way algorithm

More secure than symmetric encryption

Insertion sort

Best Case - O(n)
Average/Worst Case - O(n²)

Run-Length Encoding

Lossless data compression

Replaces consecutive data elements with the element and the number of instances

Binary tree

Worst case - O(n) when everything unbalanced

Average case - O(log n)

Best case - O(1)

O(log n) complexity type

Logarithmic

Bubble sort

Worst/average case - O(n^2)

Best case - O(1)

Merge sort

Every case - O(n log n)

O(n log n) complexity type

Logarithmic linear time

While loop

Pre-condition

Checks condition at the start of the loop

May never run if condition is already met

Do loop

Post-condition

Checks condition at the end of the loop

Always runs at least once

Stack

Allocated data structure of memory

LIFO

Can be static or dynamic

Examples:

Call stacks

Browser history for back and forwards

Undo/Redo

Operations:

isEmpty() checks if empty

push(value) adds value to the end of the list (overflow risk)

peek() returns top value from the stack

pop() removes and returns stack top value (under flow risk)

size()

isFull()

Mutable

Data can be changed at runtime

Static

Array size cannot change at runtime

Dynamic

List size can change at runtime

Array

Mutable

Static

Values stores contiguously

Contiguous

Physically adjacent and unbroken memory addresses

Lists

Mutable

Dynamic

Tuple

Immutable

Static

records

Made up of fields, a row in a table