AP Computer Science A : Program Analysis
Study concepts, example questions & explanations for AP Computer Science A
All AP Computer Science A Resources
Example Questions
Example Question #3 : Algorithm Analysis
Consider the following code:
What is the expected run time of the code (in Big-O notation?)
The run time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). This constant time operation is performed n times in the inner "for" loop, and n times in the outer "for" loop. Thus, the run time is 
Example Question #2 : Algorithm Analysis
Consider the following code:
What is the run time of the code (in Big-O notation)?
The run time can best be analyzed by breaking the code down by line. The line iterating the value of sum is performed in constant time, or O(1). This constant time operation is performed 
Example Question #4 : Algorithm Analysis
What is the BigO of the following function?
public void bigO(int[][] m){if (m.length > 2){for (int i = 0; i < m.length - 1; i++){for (int j = 0; j < m[i].length; j++){System.out.println(m[i][j]);}}}else{for (int j = 0; j < m[0].length; j++){System.out.println(m[0][j]);}}}O(n2)
O(n)
O(log(n))
O(1)
O(n*log(n)
O(n2)
The function is O(n2) because it has a nested loop of size 2, with no extras thrown in that could possibly add on a log(n). A good rule of thumb is this: if there are nested loops, then the BigO is usually O(nm), with m being the levels of loops in the longest part.
Example Question #1 : Algorithm Analysis
Which is more efficient (i.e. Lower Big O)?
1)
arr = [1, 2, 3, 4, 5, 6, 7, 8]
arr2 = [[1,2],[3,4],[5,6], [7,8], [9,10], [10, 11]]
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr2.length; j++) {
arr[i][j] = 0;
}
}
2)
arr = [1, 2, 3, 4, 5, 6, 7, 8]
arr2 = [[1,2],[3,4],[5,6], [7,8], [9,10], [10, 11]]
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr2.length; j++) {
arr[j] = 0;
}
}
1
The Big O is equivalent
2
Irrelevant
2
Code sample #1 relies on i in the second loop where int j = i. Since the code relies on i in the second loop, the order goes from O(N) to O(N2)
Code sample #2 has two separate loops that do not rely on each other. The first for loop loops through the array arr and the second for loop loops through the array arr2. Since the two loops are exclusive, the order is O(N)
Example Question #1 : Comparing Run Times
Which has faster compile time, O(N), O(N2), O(N3), or O(NlogN)?
O(NlogN)
O(N)
O(N2)
O(N3)
O(N)
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++;
}
}
b)
a) and b) have the same efficiency
Arrays are more efficient than ArrayLists
a)
a) and b) have the same efficiency
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++) {
}
}
False
True
False
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?
O( 
O( log(n) )
O(n log(n) )
None of the above
O( n )
O(n log(n) )
At first glance we might be tempted to pick O( 
Example Question #1 : Run Time Exceptions
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?
c = 0111 1111
c = 0000 0100
c = 0111 1011
c = 0111 0011
c = 0111 1011
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:
Taking both a and b and performing the operation bit by bit we get the following result:
Example Question #2 : Run Time Exceptions
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);
}
True
False
True
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.
All AP Computer Science A Resources
