Topic 19 CS Computational Thinking and Problem Solving

Binary search

method of searching an ordered list by testing the value of the middle item.

Insertion sort

method of sorting data in an array into alphabetical or numerical order.

Binary tree

hierarchical data structure with each parent node having a maximum of two child nodes.

Graph

non-linear data structure consisting of nodes and edges.

Dictionary

abstract data type consisting of key-value pairs.

Big O Notation

mathematical notation describing algorithm performance.

O(1)

Constant time complexity; efficient regardless of data set size.

O(log N)

Logarithmic time complexity; halves the data set in each pass.

O(N)

Linear time complexity; performance declines with data set growth.

O(n log N)

Linearithmic time complexity; divide data set and solve concurrently.

O(N^2)

Polynomial time complexity; efficiency reduces significantly with larger data sets.

O(2^N)

Exponential time complexity; doubles with each addition to the data set.

Recursion

a process using a function or procedure that is defined in terms of itself and calls itself.

Base case

a terminating solution to a process that is not recursive.

General case

a solution to a process that is recursively defined.

Winding

process which occurs when a recursive function or procedure is called until the base case is found.

Unwinding

process which occurs when a recursive function finds the base case and the function returns the values.

Benefits of recursion

Recursive solutions can contain fewer programming statements than an iterative solution and can solve complex problems in a simpler way.

Stack overflow

If recursive calls to procedures and functions are very repetitive, there is a heavy use of the stack, which can lead to stack overflow.

Compiler implementation of recursion

Recursive code needs to make use of the stack. Therefore, a compiler must produce object code that pushes return addresses and values of local variables onto the stack with each recursive call, winding. Then, it pops the return addresses and values of local variables off the stack, unwinding