Time complexity help

[complexTime]

Hey, I'm new to the site and also newbie in time complexity subject. I've read plenty of theoretical approaches and also some examples but I'm still having quite some troubles with determining time complexity of some of my algorhytms, especially recursion. It is quite a delicate thing so I would ask for your help if somebody can explain me through my algorhytms how to determine time complexity properly.

Here are my algorhytms:
Recursion1:

public static long rec(long n){
		if(n == 0){
			return 0;
		}
		else if(n == 1){
			return 1;
		}
		else{
			return 2*rec(n-1) + rec(n-2);
		}
	}

Iteration1:

public static long iter(long n){
		long a0 = 0, a1 = 1, tmp;
		if(n == 0){
			return 0;
		}
		else{
			for(long i=n; i>1; i--){
				tmp = a0;
				a0 = a1;
				a1 = 2*a0 + tmp;
			}
			return a1;
		}
	}

Recursion2:

public static long factorial(long n){
		if(n <= 1){
			return 1;
		}
		else{
			return n * factorial(n-1);
		}
	}
	
	public static long dominoes(long x, long y){
		return factorial(x+y) / (factorial(x)*factorial(y));
	}

Iteration2:

public static long dominoes(long x, long y){
		long temp;
		double koeficient = 0, faktor;
		if(y > x){
			temp = x;
			x = y;
			y = temp;
		}
		for(long i=0; i<=x+y; i++){
			koeficient = 1;
			for(int j=1; j<y+1; j++){
				faktor = ((double)((i+1)-j)) / (double)j;
				faktor = koeficient * faktor;
				koeficient = faktor;
			}
		}	
		return (long)koeficient;
	}

I think this one is O(x^2 + x*y) if I understood the basics but I would rather see someone more experienced determine it properly.

Recursion3:

public static String reverse(String str){
		if(str.length() <= 1 || str == null){
			return str;
		}
		return reverse(str.substring(1)) + str.charAt(0);
	}

Iteration3:

public static String reverse(String str){
		String str2 = "";
		for(int i=str.length()-1; i>=0; i--){
			str2 += str.charAt(i);
		}
		return str2;
	}

Thank you for the help.

[complexTime]

I also forgot to ask before... What is the time complexity of BigInteger (in Java)?

[Rashakil Fol]

I also forgot to ask before... What is the time complexity of BigInteger (in Java)?

Addition is O(n) where n is the number of bits in the BigInteger, and multiplication depends on the algorithm used: http://en.wikipedia.org/wiki/Multiplication_algorithm . That depends on the Java implementation. I don't know about division.

[Rashakil Fol]

Let's look at this one. I'm going to ignore the swap for now.
Iteration2:

public static long dominoes(long x, long y){
		long temp;
		double koeficient = 0, faktor;
		for(long i=0; i<=x+y; i++){
			koeficient = 1;
			for(int j=1; j<y+1; j++){
				faktor = ((double)((i+1)-j)) / (double)j;
				faktor = koeficient * faktor;
				koeficient = faktor;
			}
		}	
		return (long)koeficient;
	}

Let's add annotations, giving the cost of each line.

public static long dominoes(long x, long y){
		long temp; // O(1)
		double koeficient = 0, faktor; // O(1)
		for(long i=0; i<=x+y; i++){
			// an O(1) cost for (i <= x+y) and (i++)
			koeficient = 1; // O(1)
			for(int j=1; j<y+1; j++){
				// an O(1) cost for (j < y+1) and (j++)
				faktor = ((double)((i+1)-j)) / (double)j; // O(1)
				faktor = koeficient * faktor; // O(1)
				koeficient = faktor; // O(1)
			}
		}	
		return (long)koeficient; // O(1)
	}

When we have successive statements with cost O(x) and O(y), their combined cost is O(x + y). Let's first remove the pieces of code that we've accounted for.

public static long dominoes(long x, long y){
		// O(1)
		// O(1)
		for(long i=0; i<=x+y; i++){
			// O(1)
			// O(1)
			for(int j=1; j<y+1; j++){
				// O(1)
				// O(1)
				// O(1)
				// O(1)
			}
		}	
		return; // O(1)
	}

You'll note that the lines of code don't modify i or j. If there was some line that said "i = i * i", we wouldn't want to delete that because it would affect the number of iterations of the loop.

Now let's combine successive statements.

public static long dominoes(long x, long y){
		// O(2)
		for(long i=0; i<=x+y; i++){
			// O(2)
			for(int j=1; j<y+1; j++){
				// O(4)
			}
		}	
		return; // O(1)
	}

I've written O(2) and O(4) for didactic purposes -- really we'd just write O(1) since O(2) and O(1) are the same thing.

public static long dominoes(long x, long y){
		// O(1)
		for(long i=0; i<=x+y; i++){
			// O(1)
			for(int j=1; j<y+1; j++){
				// O(1)
			}
		}	
		return; // O(1)
	}

Now let's look at the inner loop. Its body takes O(1) time. It runs y iterations. So the running time is O(y)*O(1) = O(y).

public static long dominoes(long x, long y){
		// O(1)
		for(long i=0; i<=x+y; i++){
			// O(1)
			// O(y)
		}	
		return; // O(1)
	}

Now O(1) + O(y) = O(y) so we can combine those successive costs.

public static long dominoes(long x, long y){
		// O(1)
		for(long i=0; i<=x+y; i++){
			// O(y)
		}	
		return; // O(1)
	}

Now the outer loop runs x+y times. The interior costs O(y) time. So the cost of the loop is O(x+y) * O(y) = O((x+y)*y).

public static long dominoes(long x, long y){
		// O(1)
		// O((x+y)*y)
		return; // O(1)
	}

And O(1) + O((x+y)*y) + O(1) = O((x+y)*y).

public static long dominoes(long x, long y){
		// O((x+y)*y)
	}

And we're done.

Ignoring the swap that we decided to ignore, the cost is O((x+y)*y). But the truth is that after the swap, if it happens or not, the variable x will contain the minimum of the x and y parameters, and y will contain the maximum. So, accounting for the swap, the running time is O((min(x,y) + max(x,y)) * max(x,y)).

Are we done? We could be. But it's useful to simplify our answer. Note that 1*max(x,y) <= (min(x,y) + max(x,y)) <= 2*max(x,y). Therefore, max(x,y)^2 <= (min(x,y)+max(x,y))*max(x,y) <= 2*max(x,y)^2.

So (min(x,y)+max(x,y))*max(x,y) is Theta(max(x,y)^2) (which is a way to say the two functions are O of one another). This means we can say our function is O(max(x,y)^2) without losing any information.

Like, we could say our function is O(max(x,y)^3), and we'd lose information -- because it's a weaker bound. The fact that (min(x,y) + max(x,y))*max(x,y) is Theta(max(x,y)) means that O(max(x,y)^2) is as strong a bound.

[complexTime]

Rashakil Fol, thanks alot for your explanation. I've managed to determine the time complexity of iterative algorithms but I'm still having problems with recursion. What is the correct way to determine the time complexity of recursion?

Recursion 1:

public static long rec1(long x, long y){
		if(y == 0){
			return 1;
		}
		if(y == x){
			return 1;
		}
		return rec1(x-1, y-1) + rec1(x-1, y);
	}

Recursion 2:

public static long rec2(long n){
		if(n == 0){
			return 0;
		}
		else if(n == 1){
			return 1;
		}
		else{
			return 2*rec2(n-1) + rec2(n-2);
		}
	}

[Rashakil Fol]

Create a recursive formula for the time complexity and figure it out from there.

[complexTime]

Create a recursive formula for the time complexity and figure it out from there.

Can you please show me how to create a recursive formula?

[Rashakil Fol]

For example, suppose you have a function

int f(int n) {
  if (n == 0) {
      return 1;
  }
  else {
      return n * f(n-1);
  }
}

We want to measure its cost. But before we do so, we'll say that its cost is O(t(n)) so that we can use it in the formula.

if (n == 0) { // O(1) conditional test
      // O(1)
  }
  else {
      // O(1) + t(n-1)
      return n * f(n-1);
  }

So t(0) = O(1) and t(n) = O(1) + t(n-1)

[complexTime]

I got it now, thanks for all the help.