-1

I am studying data structures and I have hit a bit of a road block. The top is Big oh notation and it is simply confusing. While I can find the upper bound for the simplest of loops, when it comes to the more complicated stuff, I get a bit lost.

I have got this Java stack array program that I am using as practice and was hoping if some here can show me how to find its upper bound.

Code: 

import jeliot.io.*;

public class IStack {
   private int maxSize;
   private long[] stackArray;
   private int top;
   public IStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
   }
   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) {
      IStack NStack = new IStack(5); 
      NStack.push(0);
      NStack.push(1);
      NStack.push(2);
      NStack.push(3);
      NStack.push(4);
      while (!NStack.isEmpty()) {
         long value = NStack.pop();
         System.out.print("value: " + value);
         System.out.print(" ");
      }
      System.out.println("");
   }
 }
gnat
  • 21,442
  • 29
  • 112
  • 288
Liwizy
  • 19
  • 1
  • 1
    Possible duplicate of [What is O(…) and how do I calculate it?](http://programmers.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – Robert Harvey Sep 21 '16 at 22:34
  • It would help to know exactly what is confusing you. If I just say: it's O(n) does that do you any good? You'd like to know how to figure that out right? Tell us where you're getting lost. If we can see your reasoning we can steer you better. – candied_orange Sep 21 '16 at 23:19
  • I get confused when I am trying to determine the (n) with all those inner loops. – Liwizy Sep 21 '16 at 23:29
  • It's *O(1)* because your program has no input. Can you reframe your question so it's clear which operation you're trying to actually find the big-O of? – gardenhead Sep 21 '16 at 23:38
  • I see no inner loops here. Is this the best example to express your confusion? – candied_orange Sep 22 '16 at 00:02
  • Possible duplicate of [How can we calculate Big-O complexity in Functional & Reactive Programming](http://programmers.stackexchange.com/questions/220658/how-can-we-calculate-big-o-complexity-in-functional-reactive-programming) – gnat Sep 22 '16 at 05:56

1 Answers1

1

Big-O does not apply to classes. It applies to algorithms, for example methods. It is not uncommon for a data structure to have different big-O for different operation like insertion, deletion etc.

Furthermore, big-O only applies to algorithms/methods operating on an input of variable size (the n). The is only the case for push, pop and peek methods, which operates on the stack data. Methods like isFull does not operate any an input of varying size, so big-O does not apply.

The stack is using an array as the underlying storage. The methods push, pop and peek are performing a single indexed access to the underlying array. As arrays have O(1) access to elements, the methods push, pop and peek also have O(1) complexity.

This means you have a very efficient stack. But the obvious problem is the size is limited to maxSize. When the stack grows larger than this, it will just crash. So in practice you need to be able to grow the array, which will make the algorithm more interesting.

The main method is a bit tricky. Because you define the input data with a fixed size (5 element), the operation is technically also constant. There is no varying size input here. But you probably want to know the big-O of the while-loop, if the input stack is of arbitrary size. You can probably figure that out now you know pop is O(1).

JacquesB
  • 57,310
  • 21
  • 127
  • 176
  • "Big-O does not apply to classes. It applies to algorithms, for example methods." – That's not true. Big-O applies to *functions*, more precisely, it groups functions into sets based on their asymptotic growth rate. *What* those functions describe, or even *if* those functions describe anything *at all* is completely independent of Big-O. For example, you could have a function describing the average amount of lines of code in a class changed per month as a function of the number of project managers the project has, and use Big-O to describe the growth rate of that function as the number of … – Jörg W Mittag Sep 22 '16 at 12:16
  • … project managers goes to infinity. There you have a Big-O that describes a class and has absolutely nothing to do with algorithms. – Jörg W Mittag Sep 22 '16 at 12:17
  • 3
    @JörgWMittag: "In computer science, big O notation is used to classify algorithms by how they respond to changes in input size," https://en.wikipedia.org/wiki/Big_O_notation – JacquesB Sep 22 '16 at 15:06