java

1. What is the tightest upper bound in big-O notation for the function:

f(n) = 6n + 2n^2 + 55nlog(n) + 1000n^(3/2)

Hint: Do not write spaces in your answer. Use ^ for exponentiation. Use juxtaposition for multiplication (e.g. 5n, not 5*n or 5xn).

2. Consider the function:

f(n) = 12nlog(n) + 42log(n) + 19n + 67

Which of the following statements are true? (check all that apply)

f(n) is O(n)

f(n) is O(n^2)

f(n) is O(log(n))

f(n) is O(n^4)

f(n) is O(2^n)

f(n) is O(nlog(n))

3 Consider the following method:

public a(String s) { int v = 0; for(int x = 1; x < s.length; x=x+1) { if(s[x] == 'a' || s[x]=='e' || s[x] == 'i' || s[x] == 'o' || s[x] == 'u') { v = v + 1; } } return v; }

Exactly how many lines of code (statements) are executed by the method a() in the worst case? Express your answer in terms of n, the length of the string s.

Hint: simplify your final answer as much as possible, and do not put spaces in your answer. Use juxtaposition for the multiplication operator, for example to write "nine times n" write "9n" not "9xn" or "9*n"; to write "four times (n+2)" write "4(n+2)", not "4x(n+2)" or "4*(n+2)". Do not write your answer in Big-O notation. Write the exact number of lines executed.

4 Consider the following method:

public boolean isprefix(String s1, String s2) { int i = 0; if(s1.length > s2.length) return false; while(i < s1.length) { if(s1[i] != s2[i]) return false; i++; } return true; }

Exactly how many lines of code (statements) are executed by the method isprefix() in the worst case? Express your answer in terms of n, the length of the string s1.

Hint: simplify your final answer as much as possible, and do not put spaces in your answer. Use juxtaposition for the multiplication operator, for example to write "nine times n" write "9n" not "9xn" or "9*n"; to write "four times (n+2)" write "4(n+2)", not "4x(n+2)" or "4*(n+2)". Do not write your answer in Big-O notation. Write the exact number of lines executed.