Algorithms and Concurrency

Let's now look at some basics of algorithms in general, the time complexity; and the order of magnitude measurements, before we start talking about building concurrency in executing algorithms, then explore the approaches to parallelizing algorithms.

An algorithm can be defined as a sequence of steps that takes an input to produce the desired output. They are agnostic technology representations; let's look at a sorting algorithm example:

Input: A sequence of n number—a1, a2, …,an
Output: A permutation (reordering)—a1', a2', …,an' such that a1'<=a2'<=… <=an'

The following algorithm is an insertion-sort algorithm:

INSERTION-SORT(A)
1. for j = 2 to length[A]
2. dokey<-A[j]
3. //insert A[j] to sorted sequence A[1..j-1]
4. i<-j-1
5. while i>0 and A[i]>key
6. do A[i+1] <- A[i] //move A[i] one position right
7. i<-i-1
8. A[i+1]<-key

For measuring the time and space complexity...