Show Menu

COMP250 Cheat Sheet by


unambi­guous procedure executed in a finite number of steps
What makes a good algorithm?
Correc­tness, Speed, Space, Simplicity
time it takes to solve problem
amount of memory required
easy to unders­tand, easy to implement, easy to debug, modify, update

Running Time

measur­ement of the speed of an algorithm
Dependent variables:
size of input & content of input
Best Case:
time on the easiest input of fixed size
Average Case:
time on average input
good measure, hard to calculate
Worst Case:
time on most difficult input
good for safety critical systems, easy to estimate

Loop Invariants

loop property that holds before and after every iteration of a loop.
1. Initia­liz­ation
If it is true prior to the iteration of the loop
2. Mainte­nance
If it is true before an iteration of the loop, it remains true before the next iteration
3. Termin­ation
When the loop termin­ates, the invariant gives us a useful property that helps show the algorithm is correct

In Place Sorting

Uses only a constant amount of memory in addition of that used to store the input
Great for large data sets that take up large amounts of memory
Selection Sort, Insertion Sort (Only moving elements around the array)
Not in place: new array required


Algorithm partition(A, start, stop)
Input: An array A, indices start and stop.
Output: Returns an index j and rearranges the elements of A
such that for all i<j, A[i] ! A[j] and
for all k>i, A[k] " A[j].
pivot # A[stop]
left # start
right # stop - 1
while left ! right do
while left ! right and A[left] ! pivot) do left # left + 1
 while (left ! right and A[right] " pivot) do right # right -1
if (left < right ) then exchange A[left] $ A[right]
exchange A[stop] $ A[left]
return left
Time Comple­xities:
• Worse case:
– Already sorted array (either increasing or decrea­sing)
– T(n) = T(n-1) + c n + d
– T(n) is O(n2)
• Average case: If the array is in random order, the
pivot splits the array in roughly equal parts, so the
average running time is O(n log n)
• Advantage over mergeSort:
– constant hidden in O(n log n) are smaller for quickSort.
Thus it is faster by a constant factor
– QuickSort is easy to do “in-place”


choose an element of the array for pivot
divide into 3 sub-gr­oups; those smaller, those larger and those equal to pivot
recurs­ively sort each group
concat­enate the 3 lists

Proofs by Induction (Examples)


Object Orientated Progra­mming

User defined types to complement primitive types
Called a class
Data & methods
Static members:
members shared by all objects of the class

Recursion Progra­mming

using methods that call themselves
base case
a simple occurrence that can be answered directly
recursive case
A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurr­ences of the same problem.

Divide & Conquer

the problem into sub problems that are similar to the original but smaller in size
the sub-pr­oblems by solving them recurs­ively. If they are small enough, solve them in a straig­htf­orward manner
the solutions to create a solution to the original problem

BIG O Definition

f(n) & g(n) are two non negative functions defined on the natural numbers N
f(n) is O(g(n)) if and only if:
there exists an integer n0 and a real number c such that Ɐn>= n0 f(n) <= c * g(n)
N.B. The constant c must not depend on n

Big O Visual­ization

Big O Recurrence

Sum of ai from 0 to n = (a(n+1) -1 )/(a-1)

Limita­tions of Arrays

Size has to be known in advance
memory required may be larger than number of elements
inserting or deleting an element takes up to O(n)

ADT: Queues

FIFO(First in first out)
Any first come first serve service
enqueue() - add to rear
dequeue() - removes object at front
front() - returns object at front
size() - returns number of objects O(n)
isEmpty() - returns true if empty
Double Ended Queues­(de­que): Allows for insertions and removals from front and back
- By adding reference to previous node - removals occur in O(1)

ATD: Stacks

Operations allowed at only one end of the list (top)
LIFO: (Last in first out)
push() - inserts element at top
pop() - removes object at top
top() - returns top element without removing it
size() - returns number of elements
isEmpty() - returns True if empty
page visited history in web browser
JVM - keeps track of chain of active elements (allows for rec)
space used: O(n)
operat­ions: O(1)
max size must be defined prior
pushing to a full stack causes implem­ent­ation specific error


BinarySearch(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
        mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else if (A[mid] < value)
              low = mid + 1
              return mid
      return not_found // value would be inserted at index "low"
value > A[i] for all i < low 
value < A[i] for all i > high

Worst case perfor­mance: O(log n)
Best case perfor­mance: O(1)
Average case perfor­mance: O(log n)

Binary­Search (Recur­sive)

int bsearch(int[] A, int i, int j, int x) { 
if (i<j) {
int e = [(i+j)/2];
if (A[e] > x) {
return bsearch(A,i,e-1);
} else if (A[e] < x) {
return bsearch(A,e+1,j);
} else {
return e;
} else { return -1; }	
Time Comple­xity: log(ba­se2)(n)

Insertion Sort (Itera­tive)

For i ← 1 to length(A) - 1
 j ← i
 while j > 0 and A[j-1] > A[j]
 swap A[j] and A[j-1]
 j ← j - 1
 end while
end for
Time comple­xity: O(n2)


Algorithm ListIntersection (A,m, B,n)
Input: Same as before
Output: Same as before
inter ← 0
Array C[m+n];
for i ← 0 to m-1 do C[i] ← A[i];
for i ← 0 to n-1 do C[ i+m ] ← B[i];
C ← sort( C, m+n );
ptr ← 0
while ( ptr < m+n-1 ) do {
 if ( C[ptr] = C[ptr+1] ) then {
 inter ← inter+1
 ptr ← ptr+2
 else ptr ← ptr+1
return inter
Time Comple­xity: (m+n) * (log(­m+n)) + m + n -1

MergeSort (Recur­sive)

MergeSort (A, p, r) // sort A[p..r] by divide & conquer
if p < r
   then q ← ⎣(p+r)/2⎦
      MergeSort (A, p, q)
      MergeSort (A, q+1, r)
      Merge (A, p, q, r)
Time Comple­xity: 2T(n/2) + k • n + c’

Primitive Operations

calling method
returning from method
compar­isons of primitive types
indexing into array
following object reference
Assume each primitive operation holds the same value = 1 primitive operation

Prove Big - Oh



No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.