What is the big O of the four following methods public static String method1(int

Question

What is the big O of the four following methods

public static String method1(int n)
{
if (n < 0) throw new IllegalArgumentException();
if (n <= 0)
return "*";
else {
String s = method1(n - 1);
return s + s;
}

}
public static int method2(int n)
{
if (n < 1) throw new IllegalArgumentException();
if (n == 1)
return 2;
else
return method2(n - 1) * (2 * n);
}
public static void method3(int n)
{
if (n < 1) throw new IllegalArgumentException();
if (n == 1)
System.out.print("1");
else {
method3(n - 1);
System.out.print(", " + n);
}
}
public static void method4(int n)
{
if (n < 1) throw new IllegalArgumentException();
if (n==1) System.out.print(1);
else if (n==2) System.out.print("1 1");
else {
System.out.print((n+1)/2+ " ");
method4(n-2);
System.out.print(" "+(n+1)/2);
}
}
}

Are they all O(n)?

Explanation / Answer

Answer:

Yes all the four methods have the running time as O(n) since in each method the if condition is executed for "n" times until the condition is satisfied or else condition is executed if the condition of if statement fails.The if condition is executed n times since the input parameter which is passed is has more number of values which is executed one by one.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.