My instructor has asked me to analyze my algorithm. The assignment was to write a program that takes in a list of numbers as user input, and finds the longest sequence of like-numbers, marks the number, and marks the starting index. That part is done, but if anyone has any comments on my code, those are welcome too. Below are his instructions:

Analysis of algorithms is the determination of the amount of time and space resources required to execute it. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity. However, the main concern of analysis of algorithms is the required time or performance. Generally, we perform the following types of analysis −

• Worst-case − The maximum number of steps taken on any instance of size n.

• Best-case − The minimum number of steps taken on any instance of size n.

• Average case − An average number of steps taken on any instance of size n.

TLDR; Would my algorithm be O(n) because the program has to iterate through the entire list once? Also does my while loop affect algorithm efficiency?

import java.util.ArrayList;
import java.util.Scanner;

public class Practice {

    public static void main(String[] args) {
        
        Scanner keyboard = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<Integer>();
        String temporaryNumber;

        System.out.println("Enter a list of integers, when done, enter 0:");
        while(true) {
            try {
                int j = 0;
                temporaryNumber = keyboard.next();
                int permNumber = Integer.parseInt(temporaryNumber);
                list.add(permNumber);
                j  ;
                System.out.println(list); // Displays list as it's typed, OPTIONAL
                if (permNumber == 0) {
                    break;
                }
                else if (permNumber < 0) {
                    System.out.println("Input must be a positive integer.");
                    list.remove(j);
                }
            }
            catch (NumberFormatException e) {
                System.out.println("Input must be a positive integer.");
            }
        }
        keyboard.close();
                int sequenceCount = 1;
                int highestSequenceCount = 0;
                int longestSeqInteger = 0;
                int startingIndexCount = 0;
        
        for (int i = 1; i < list.size() -1; i  ) {
                if (list.get(i) == list.get(i-1)) {
                    sequenceCount  ;
                }
                else {
                    
                    if (highestSequenceCount < sequenceCount) {
                        highestSequenceCount = sequenceCount;
                        longestSeqInteger = list.get(i-1);
                        startingIndexCount = i - highestSequenceCount;
                        sequenceCount = 1;
                    }
                    else {
                        sequenceCount = 1;
                }
            }
        }
        System.out.println("The longest same number sequence starts at index "   startingIndexCount   ", with "   
        highestSequenceCount   " values of "   longestSeqInteger); //temp
    }
}

CodePudding user response：

Also does my while loop affect algorithm efficiency?

You need to take all operations of the program into account, so yes, the while loop too. The while loop iterates over all inputs (including rejected ones and the input terminator) once.

Would my algorithm be O(n) because the program has to iterate through the entire list once?

It iterates through the whole list twice (see above), but doing it once versus twice is a matter of a constant scale factor, so that in itself does not make a difference in the asymptotic bound.

Before you can conclude that a constant number of iterations over the input can be completed in O(n) steps, you need to consider how much work is performed on each iteration, and in particular, whether that is a function of the size of the input. That's a separate analysis for each of your loops. If the work done on each iteration is independent of n then the cost of that per-iteration work is O(1), and the cost of n iterations is therefore n * O(1) = O(n).

CodePudding user response：

Your while loop

• reads input from the user,
• does some processing (not only storing into a list, but also removing elements under specific circumstances),
• does some output with it.

Having user input in an "algorithm" makes it impossible to reason about its performance, as you typically measure the user's typing speed and not your program efficiency. And I wouldn't dare to assume human typing speed to be constant.

So, first define what is part of your algorithm and what not (exclude input and output, keep all computation), and ideally make that a method of its own. I guess, that will be the for loop, more or less.

Then, Big-O notation talks about the increase in run-time, depending on "the input size", so define what "input size" means in your context - most plausibly, the size of the list. Call that n.

O(n) means that (asymptotically) doubling the n value results in twice the run time. You should be able to evaluate that...

It's crucial to define what n means in the context of your algorithm and to choose wisely. If you e.g. define n to be the largest of the input numbers, you'll probably find out that this doesn't have any influence on the algorithm's run time, so you'd get an O(1) result - useless because of an ill-defined n.