1. What does the following code fragment print (without running the program on a

Question

1. What does the following code fragment print (without running the program on a computer)? (2

points)

int[] a = new int[10];

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

a[i] = 9-i;

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

a[i] = a[a[i]];

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

System.out.println(i);

2. Write an algorithm in pseudo code for checking whether a number from user input is a prime

number. Your algorithm should print "XXX is a prime number" or "XXX is not a prime number" in

which "XXX" is the number that user inputs. Please make sure that your algorithm is written in

general term containing all the necessary components of an algorithm, state all your assumptions

(e.g. algorithm name, pre-condition, post-condition, etc.) (4 points)

3. Identify the big Oh notation for each of the following functions (1 point each).

a. 17

b. 3logn

c. 20n-4

d. 12nlogn+1000n

e. 3n2 + 5n -2

f. 8n3 + 3000000n2

g. 2(n+2) + 18n2 + 3n

4. For each of the program segment below, identify the complexity in Big O notation (1 point):

a) // Fragment 1

sum = 0;

for (i=1; i<=n; i=i*5)

for (j=1; j<=n; j = j+2)

sum++;

b) // Fragment 2

sum = 0;

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

sum++;

for (int j=n; j>0; j--)

sum--;

c) // Fragment 3

sum = 0;

for (i=n; i>=1; i--)

for (j=1; j<=i ; j++)

sum++;

d) // Fragment 4

sum = 0;

for (i = 1; i<=n; i++)

for (j = 1; j<=100; j++)

sum++;

5.

Identify the complexity in Big O notation for the program segment below (2 point):

sum = 0;

for (i = 1; i<=10; i++)

for (int j=1; j<=2^n; j++)

sum++;

Explanation / Answer

1).

0
1
2
3
4
5
6
7
8
9

2).

public void isPrime(){
          int temp;
           boolean isPrime=true;
          
           int num <- Capture the Input
           for(int i=2;i<=num/2;i++)
           {
       temp=num%i;
           if(temp==0)
           {
           isPrime=false;
           break;
           }
           }
           //If isPrime is true then the number is prime else not
           if(isPrime)
           System.out.println(num + " is Prime Number");
           else
           System.out.println(num + " is not Prime Number");
   }

3).

a. O(1)
b. O(logn)
c. O(n)
d. O(nlogn)
e. O(n^2)
f. O(n^3)
g. O(n^2)(if it is given 2*(n+2) in question) or if it is 2^(n+2) is given in question then O(2^n)

4).

a. O(nlogn) base of log is 5
b. O(n)
c. O(n^2)
d. O(n)

5).

O(2^n)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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