Java Stack array - Big O notation

Question

What are the big o notation for this code below. I still couldn't grasp the concept fully. I am supposed to get a thought from experienced coders to give a summary for the big o performance based on this code.

import java.util.*;
import java.util.InputMismatchException;
import javax.swing.*;
public class MyStack {

   private int maxSize;
   private long[] stackArray;
   private int top;
   public MyStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
      System.out.println("Push onto stack");
   }
   public long pop() {
      return stackArray[top--];
   }
   public long peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == maxSize - 1);
   }
   public static void main(String[] args) {
        Scanner num = new Scanner(System.in);
        int input =0;
        int x;
        MyStack theStack = new MyStack(5); 
    for(x=0; x<5; x++)
    {


        System.out.println("\nEnter a number(Push): ");
        input = num.nextInt();
        theStack.push(input);



      } 



     System.out.print("The first element on the top is the top of the stack");
     System.out.println("");
      while (!theStack.isEmpty()) {
         long value = theStack.pop();
         System.out.print(value);
         System.out.println(" Pop");

      }


      System.out.println("");

   }
}

Answer 1

Big O performance varies by the operation that you're attempting. Look at your "isEmpty()" method. It always just looks at the value of top, so that's constant, or O(1). I don't see other methods in your class (except main(), which we'll look at in a minute) that have any dependency on the number of elements in the array, they all just work with top.

main() just asks for 5 values, then prints them out. If it asked for 50, it would take ten times longer (assuming that user input remained relatively constant). So main is O(n) where n is the number of elements in the array.

If you were looking for a particular number in the array, you'd likely have to examine each one in turn, so O(n).

And if you were doing something more complicated where you looked at each element and then did some operation or comparison with each other element (e.g. with a nested for loop) you'd end up with O(n^2).

Hope that helps your thought process.

Answer 2

The performance of all your methods are in O(1) as they are merely indexing an array or checking against the value of top.

In the body of main the for loop is executed 5 times, performing 5 pushes, thus O(5 * 1) = O(n) because the stack has size n = 5.

Afterwards the while loop will pop the stack until it's empty. Because the stack can only contain 5 elements(which is also the size of it) this is again O(5 * 1) = O(n) again.

So you can assume it is in O(2 * n) which yields O(n).

Answer 3

Data structure complexity of an operation is always calculated against the number of element it holds, is shows maximum time it will take with the increase the number of elements.

Eg : How much time will it take to search an element in "B-Tree" given that there exists n number of elements already in it.

In B-Tree search time is O(log n), means that the maximum search time will grow as a function of log n (see the Big-O Complexity graph).

In your case to implement the stack you have used an array and you have multiple oprations, but your operations does not depend on the element which carry in your stack, because complexity of get an element in a specific location is O(1). So all your operation takes O(1) time.

push - O(1)

pop - O(1)

isFull - O(1)

isEmpty - O(1)

But if you implement search in your stack, check whether given long is in your stack then the search depends on the elements where you have to iterate all the elements and the complexity will be O(n).