Hello, I'm new to the whole concept of using Big O notation for runtime analysis and I was wondering if anyone could tell me if I'm analyzing my code correctly. I vaguely understand the concept of Big O and I'm trying to analyze it based on what I do understand so any help would be appreciated.
For the following snippets keep in mind that my int num is obtained through user input.
Here is an iterative method from my code:
/**
* This method uses a loop to see if there is a remainder of 0 when
* num is divided by each number less than num, but greater than 1. If
* there is a remainder for all of the numbers then num is prime. If
* there isn't a remainder for any of the numbers then num is not prime.
*
* @param num integer greater than 1 inputed by user.
*/
public static void IterativePrimeCheck(int num) {
for(int i=num-1; i>1; i--) {
if(num % i == 0) { //If there is no remainder num isn't prime
System.out.println("Iterative: " + num + " is not a prime number.");
return; //if num isn't prime return
}
}
//If n makes it through the loop, then it is prime
System.out.println("Iterative: " + num + " is a prime number.");
}
Okay, so from my understanding I believe this is considered a constant since we can't tell what num is going to be. And regardless if its 1 or 1000 it is still considered O(1) since it is constant correct? So the Runtime for my iterative loop would be O(1) correct?
Here is my recursive method:
/**
* This method uses a recursion to see if there is a remainder of 0 when
* num is divided by each number less than num, but greater than 1. If
* there is a remainder for all of the numbers then num is prime. If
* there isn't a remainder for any of the numbers then num is not prime.
*
* @param num integer greater than 1 inputed by user.
* @param temp integer that is equal to num and decremented when method is called
* @return true if the num is prime and false if num is not prime
*/
public static boolean RecursivePrimeCheck(int num, int temp) {
temp--; //decrement temp each time method is called
if(temp > 1) { //keep recurring as long as temp is larger than 1
if(num % temp == 0) return false; //if n % temp is 0 then n isn't prime
else return RecursivePrimeCheck(num,temp); //if temp > 1 and n % temp isn't 0, keep recurring
}
else return true; //temp is equal to 1. n % temp never equals 0. Therefore n is prime.
}
This uses basically the same concept as the iterative method since we can't determine what num is correct? Therefore the runtime would also be O(1)?
My entire program:
/**
* Program gets an integer from the user and
* determines whether the number is prime or
* not using an iterative method and a recur-
* sive method.
* @author Kinsey, Anthony
* @assignment ICS 211 Assignment 2
* @date 01/29/08
* @bugs No known bugs.
*/
// When the integer 344587 is entered, my program determines that it is a prime number
// Machine: Apple Macbook 2GHz Intel Core Duo
// Memory: 2GB 677MHz DDR2 SDRAM
// IDE: Eclipse
import java.util.Scanner;
import java.util.InputMismatchException;
public class Prime {
public static void main(String[] args) {
//** declare scanner keyboard*/
Scanner keyboard = new Scanner(System.in);
//** define integer to hold input */
int userInt = 0;
//Prompt for input
System.out.print("Please enter an integer larger than 1: ");
//Check if user enters an integer
try {
//set userInt to user inputed integer
userInt = keyboard.nextInt();
//make sure the integer is larger than 1
if(userInt < 2) {
System.out.println("Integer must be larger than 1.");
System.exit(1); //exit if not
}
}
catch(InputMismatchException ime) { //catch the exception if they don't enter an integer
System.out.print("You did not enter an integer.");
System.exit(1);//exit if they don't enter an integer
}
IterativePrimeCheck(userInt);
//if the RecursivePrimeCheck method returns true, userInt is prime
if(RecursivePrimeCheck(userInt,userInt)) {
System.out.println("Recursive: " + userInt + " is a prime number.");
}
else { //if not userInt is not prime
System.out.println("Recursive: " + userInt + " is not a prime number.");
}
}
/**
* This method uses a loop to see if there is a remainder of 0 when
* num is divided by each number less than num, but greater than 1. If
* there is a remainder for all of the numbers then num is prime. If
* there isn't a remainder for any of the numbers then num is not prime.
*
* @param num integer greater than 1 inputed by user.
*/
public static void IterativePrimeCheck(int num) {
for(int i=num-1; i>1; i--) {
if(num % i == 0) { //If there is no remainder num isn't prime
System.out.println("Iterative: " + num + " is not a prime number.");
return; //if num isn't prime return
}
}
//If n makes it through the loop, then it is prime
System.out.println("Iterative: " + num + " is a prime number.");
}
/**
* This method uses a recursion to see if there is a remainder of 0 when
* num is divided by each number less than num, but greater than 1. If
* there is a remainder for all of the numbers then num is prime. If
* there isn't a remainder for any of the numbers then num is not prime.
*
* @param num integer greater than 1 inputed by user.
* @param temp integer that is equal to num and decremented when method is called
* @return true if the num is prime and false if num is not prime
*/
public static boolean RecursivePrimeCheck(int num, int temp) {
temp--; //decrement temp each time method is called
if(temp > 1) { //keep recurring as long as temp is larger than 1
if(num % temp == 0) return false; //if n % temp is 0 then n isn't prime
else return RecursivePrimeCheck(num,temp); //if temp > 1 and n % temp isn't 0, keep recurring
}
else return true; //temp is equal to 1. n % temp never equals 0. Therefore n is prime.
}
}
I'm not sure I totally grasp the concept but from my understanding since both methods are constants O(1). The entire runtime of my program is O(1)?
If anyone could correct me or help me understand this concept I would greatly appreciate it. Thank you in advance!