Exercise 1. Please show the big O notation of the recurrence relation below (please show detailed steps for full credits): T(n) = T(n-1) + n

Exercise 2. What is the big O notation of the following program (please show detailed steps for full credits): for (int i=n; i>0; i-=2) for (int j=i; j

Exercise 3. Write a java program that prompts the user to enter a string and displays the maximum consecutive increasingly ordered substring. For example, if the input string is "abcabcdgabmnsxy", then the maximum increasingly ordered substring is "abmnsxy". Analyze the time complexity of your program.

Hint. charAt(int i) returns the character of the current String object at index i. For example: "soMeStriNG".charAt(2) returns M.

Exercise 4. Find the non-recursive version of the following recursive function. Which version is better?

static long tough(int x, int y) {

if (x < y) return tough(y, x);

else if ( y <= 0 ) return 1;

else { if (x > y) return tough(x - 1, y) + tough(x - 1, y - 1);

else // it means x == y return tough(x - 1, y - 1);

}

}