/*
This program demonstrates some different algorithms and their time
complexity. You should run this program, then tweak it and run it
again. The tweak is to the size of the array. Don't make it very
big or the first method (f1) may never finish!
*/
public class TimeComplexity
{
public static int count = 0;
public static final int SIZE = 3;
public static void main(String [] args)
{
Comparable [] array = new Comparable[SIZE];
System.out.println("Here comes f1...\n");
f1(array.length);
System.out.println("\nHere comes f2...\n");
f2(array);
System.out.println("\nHere comes f3...\n");
f3(array);
System.out.println("\nHere comes f4...\n");
f4(array);
}//end main
//--------------------------------------------------------------------
// time complexity 3^n
/* Each call to this recursive methods generates three more calls.
Each of those calls in turn generates three more of their own.
So, 1 call leads to 3, leads to 9, leads to 27, leads to 81, etc.
which is 3^n (exponential).
*/
public static void f1(int n)
{
count++;
System.out.println("f1 just called -- count is: " + count);
if (n > 0)
{
f1(n-1);
f1(n-1);
f1(n-1);
System.out.println("n is: " + n + ", count is: " + count);
}//end if
else
System.out.println("Reached base case, count is: " + count);
}//end f1
//--------------------------------------------------------------------
// time complexity nlog2n (outer loop is log2n, inner is n)
/*
Outer loop has i divided by 2 each time -- repetitive division by 2 is
log2n. The inner loop runs n times (ok, n-1), but n is the dominant term.
Since the outer loop drives the inner, we have log2n*n, but it's clearer
to write the dominant term in an expression first, so we just say
nlog2n.
*/
public static void f2(Comparable [] array)
{
int i, j;
for (i=array.length; i>0; i = i/2)
{
for (j=1; j < array.length; j++)
{
System.out.println("i: " + i + ", j: " + j);
}//end j loop
}//end i loop
}//end f2
//--------------------------------------------------------------------
// time complexity is n^2
/*
Outer loop goes n times. Inner loop execution depends on outer.
It first goes n times, then n-1, then n-2, down to 1. This sequence
can be represented by the formula: n(n-1)/2. When multiplied out,
the dominant term in is n^2
*/
public static void f3(Comparable [] array)
{
int i, j;
for (i=0; i < array.length; i++)
for (j = i; j < array.length; j++)
System.out.println("i: " + i + ", j: " + j);
}//end f3
//--------------------------------------------------------------------
//time complexity is n^2log2n
/*
The j and k loops together give us n^2 for the same reason as f3() above.
The i loop executes log2n times, so we have log2n*n^2, but we write the
biggest term first, so n^2log2n
*/
public static void f4(Comparable [] array)
{
int i, j, k;
for (i=array.length; i>0; i = i/2)
for (j=0; j < array.length; j++)
for (k = j; k < array.length; k++)
System.out.println("i: " + i + ", j: " + j + ", k: " + k);
}//end f4
}//end class TimeComplexity