Computer Science : Algorithm Analysis

Study concepts, example questions & explanations for Computer Science

varsity tutors app store varsity tutors android store

Example Questions

2 Next →

Example Question #1 : Comparing Run Times

Which has faster compile time, O(N), O(N2), O(N3), or O(NlogN)?

Possible Answers:

O(N)

O(N2)

O(NlogN)

O(N3)

Correct answer:

O(N)

Explanation:

O(NlogN) is O(N) * O(logN) which is greater than O(N) alone.

O(N2) is O(N*N) which is greater than O(N).

O(N3) is O(N*N*N) which is greater than O(N).

O(N) is the smallest and therefore is the quickest to compile. Therefore, O(N) is the correct answer.

Example Question #2 : Comparing Run Times

Which is more efficient?

 

a) 

arr = [0, 1, 2, 3]

for (int i = 0; i < arr.length; i++) {

int j = 0;

if (j == arr[i]) {

j++;

}

}

 

b)

ArrayList<Integer> arL = new ArrayList<Integer>();

arL.add(0);

arL.add(1);

arL.add(2);

arL.add(3);

 

for (int i = 0; i < arL.size(); i++) {

int k = 0;

if (k == arL.get(i)) {

k++;

}

}

 

Possible Answers:

b)

Arrays are more efficient than ArrayLists

a)

a) and b) have the same efficiency

Correct answer:

a) and b) have the same efficiency

Explanation:

The two code snippets have the same efficiency. Both operate in O(N) time. ArrayLists use arrays as their underlying data structure so access to the data is also the same. 

Example Question #3 : Comparing Run Times

True or False.

The code snippet A has a more efficient running time than code snippet B.

 

(A)

for (int i = 0; i < 25; i++) {

for (int j = i; j < 25; j++) {

 

}

}

 

(B)

for (int i = 0; i < 25; i++ {

for (int j = 0; j < 25; j++) {

 

}

}

Possible Answers:

True

False

Correct answer:

False

Explanation:

Code snippet A has a running time of O(N2). Code snippet B has a running time of O(N). While the two code snippets may look the same, the second for loop in code snippet A sets j=i. Since j is relying on i, it's multiplying the first for loop's running time by the second for loop's running time. This gives us O(N*N) or just O(N2). 

Example Question #1 : Comparing Run Times

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

    for( int j = 1; j < n; j *= 2){

        someFunction();

    }

}

 

For the code above, what is the run time in Big O notation?

Possible Answers:

None of the above

O(  )

O( log(n) )

O( n )

O(n log(n) )

Correct answer:

O(n log(n) )

Explanation:

At first glance we might be tempted to pick O(  ) because there are 2 for loops. But, upon closer inspection we can see that the first loop will yield a O( n ) running time but the second loop does not. The second loop has only an O( log(n) ) running time because "j" doubles each iteration and does not increase linearly. That will yield O( log(n) ) since O( log(n) ) is a much faster running time. So the final result is O( n log(n) ).

Example Question #11 : Algorithm Analysis

BITWISE XOR OPERATION

Given the following binary values

a = 0100 1110

b = 0011 0101

perform an XOR operation (c = a^b). What is the result?

Possible Answers:

c = 0111 1011

c = 0000 0100

c = 0111 0011

c = 0111 1111

Correct answer:

c = 0111 1011

Explanation:

Performing a bitwise excludive OR constitutes in taking both binary values and evaluating as follows: either one or the other (1) never both (0). This is the truth table for a bitwise XOR operation:

 Blank flowchart   new page  2

Taking both a and b and performing the operation bit by bit we get the following result:

 Result

Example Question #12 : Algorithm Analysis

True or False.

 

There is a runtime exception in this code snippet. 

 

int wait_time = 0;

int wait_time = 5;

for (int i = 0; i < wait_time; i++) {

System.out.println(wait_time);

}

Possible Answers:

True

False

Correct answer:

True

Explanation:

Yes, there is a runtime exception in the code snippet. The int wait_time is defined twice which will give a runtime exception. This can be fixed by not declaring int before the second assignment of the variable wait_time. 

2 Next →
Learning Tools by Varsity Tutors