Question 1: (15 marks)

What is the running time (Big-O notation) for each of the following program fragments?

Explain your result in each part.

a- public static String reverse3(String s)

{

int N = s.length();

char[] a = new char[N];

for (int i = 0; i < N; i++)

a[i] = s.charAt(N-i-1);

return new String(a);

}

b- int sum = 0;

for(int i=1;i

for(int j=1;j

for(int k=1;k

if (j % i==1)

sum++;

c- public static String reverse1(String s)

{

int N = s.length();

count=0;

String reverse = " ";

for (int i = 0; i < N; i++)

reverse = s.charAt(i) + reverse;

for (int j=0;j

count++;

return reverse;

}