Please enable JavaScript to use CodeHS

AP Computer Science A Textbook

1. Primitive Types

2. Using Objects

3. Boolean Expressions and if Statements

4. Iteration

4.1 while Loops

4.2 for Loops

4.3 Developing Algorithms Using Strings

4.4 Nested Iteration

4.5 Informal Code Analysis

Algorithms

Program Efficiency

Statement Execution Count

Loop Execution Count

while Loop Time

for Loop Time

Check Your Understanding

Exercise: Improving findChar Speed

5. Writing Classes

6. Arrays

7. ArrayLists

8. 2D Arrays

9. Inheritance

10. Recursion

Chapter 4

Iteration

4.5 Informal Code Analysis

Throughout this course, you have spent a considerable amount of time developing algorithms. Algorithms are a step-by-step process that solves a problem. Many, if not all, of the programs that you have developed, are considered algorithms because they solve a problem.

Algorithms

You also use algorithms in our daily lives and don’t think about it. Most of the tasks that you perform on a daily basis are routinized and have procedures that you follow so that you can complete them as planned. Making a PBJ sandwich is an example of a practice that you do that has a procedural, step-by-step nature.

makePBJ()
{
    takeBread();
    spreadJelly();
    spreadPeanutButter();
    if (likeToasted){
        toast();
    }
}
Plain text

So what makes a good algorithm?

  • Correctness
  • Easy to understand by someone else
  • Efficiency (run time and memory requirements)

Correctness refers to whether the algorithm solves the given problem. Easy to understand can be a function of how the code is laid out, using appropriate variable names, and the use of comments. Efficiency can be looked at in several ways, which you will explore in this section.

Program Efficiency

Program efficiency is important because it affects both the speed and cost to execute a program. Oftentimes speed and cost are impacted by the physical computer’s specification and as a programmer, you do not have much control over this.

To help estimate the cost and efficiency of a program, you can use an informal code analysis by looking at the number of statements that a program needs to execute. A statement execution count indicates the number of times a statement is executed by the program, which can be a good indicator of the cost and speed of the program.

Statement Execution Count

The Statement Execution Count is the number of times a statement is executed by the program. When comparing different algorithms, you can estimate the costs for each by looking at the number of statements that need to be executed to run the program.

An execution statement might refer to:

  • an arithmetic operation ( + , * )
  • an assignment (int value = 2)
  • a test (x == 0)
  • an input/output

Take a look at the example below:

public void computeSum (int n) {
    int sum = 0; 
    int n = 10;

    for (int i = 0; i < n; i++) {
        sum += i; 
    }
    System.out.println(sum); 
}
Plain text

In this example, the code executes the first two assignment statements before the loop. Then the loop executes n times, followed by one additional statement. The total number of steps executes for this algorithm would be n + 3.

Loop Execution Count

With a nested loop, the number of statement executions for the loops needs to be multiplied together. Take some time to explore this example:

while Loop Time

for Loop Time

Check Your Understanding

  1. Incorrect Correct No Answer was selected Invalid Answer

    How many times does the following loop iterate?

    // x has been initialized with a positive int value
for (int count = 0; count <x; count++) 
{
    System.out.print("*");
}
    Java

Exercise: Improving findChar Speed

The following code is the implementation for the findChar() method, which figures out if a character is in a String.

public boolean findChar(String string, String key)
{
    for(int index = 0; index < string.length(); index++)
    {
        String character = string.substring(index,index+1);
        if(character.equals(key))
        {
            return true;
        }
    }
        return false;
}
Plain text

However, there is a much more efficient and simple algorithm that we can use to determine if a character is in a String. Using the method signature public boolean findChar(String string, String key), figure out a more efficient method with a lower execution count.

Hint: We’ve learned a couple of methods that can tell us what index a character is at - can we use those to determine if the character is in a String?