What is the execution time Big-O for each of the methods in the Queue-1.java interface for the ArrayQueue-1.java and CircularArrayQueue-1.java implementations?
Hello, i need help with understanding Big-O.
What is the execution time Big-O for each of the methods in the Queue-1.java interface for the ArrayQueue-1.java and CircularArrayQueue-1.java implementations?
Short Big-O reminders:
- Big-O is a measure of the worst case performance (in this case execution time).
- O(1) is constant time (simple assignment statements)
- O(n) is a loop that iterates over all of the elements.
- O(n2) is one loop nested in another loop, each of which iterates over all the elements.
- If a method calls another method, what happens in the called method must be taken into consideration.
Queue.java
public interface Queue<E> {
/**
* The element enters the queue at the rear.
*/
public void enter(E element);
/**
* The front element leaves the queue and is returned.
* @throws java.util.NoSuchElementException if queue is empty.
*/
public E leave();
/**
* Returns True if the queue is empty.
*/
public boolean isEmpty();
/**
* Returns the front element without removing it.
* @throws java.util.NoSuchElementException if queue is empty.
*/
public E front();
}
ArrayQueue.java
import java.util.NoSuchElementException;
import java.util.StringJoiner;
/**
* A queue implementation that uses an array (not circular).
*
* @author (your name)
* @version (a version number or a date)
*/
public class ArrayQueue<E> implements Queue<E> {
private static final int DEFAULT_CAPACITY = 100;
private static final int FRONT = 0;
private int rear; // Index of the next available cell of the queue
private E[] queue;
public ArrayQueue(int initialCapacity) {
queue = (E[]) new Object[initialCapacity];
rear = FRONT;
}
public ArrayQueue() {
this(DEFAULT_CAPACITY);
}
@Override
public void enter(E element) {
// Implement as part of assignment
}
CircularArrayQueue.java
import java.util.NoSuchElementException;
import java.util.StringJoiner;
/**
* A queue implemented using a circular buffer.
*
* @author (your name)
* @version (a version number or a date)
*/
public class CircularArrayQueue<E> implements Queue<E> {
public static final int DEFAULT_CAPACITY = 100;
private int front; // Index of the front cell of the queue
private int rear; // Index of the next available cell of the queue
private E[] queue; // Circular buffer
public CircularArrayQueue(int initialCapacity) {
queue = (E[]) new Object[initialCapacity];
front = 0;
rear = 0;
}
public CircularArrayQueue() {
this(DEFAULT_CAPACITY);
}
@Override
public void enter(E element) {
// Implement as part of assignment
}
@Override
public E leave() throws NoSuchElementException {
// Implement as part of assignment
}
@Override
public E front() throws NoSuchElementException {
// Implement as part of assignment
}
@Override
public boolean isEmpty() {
// Implement as part of assignment
}
private boolean isFull() {
// Implement as part of assignment
}
private int incrementIndex(int index) {
return (index + 1) % queue.length;
}
private void expandCapacity() {
// Implement as part of assignment
}
@Override
public String toString() {
StringJoiner result = new StringJoiner("[", ", ", "]");
for (int i = front; i != rear; i = incrementIndex(i)) {
result.add(queue[i].toString());
}
return result.toString();
}
}
The worst-case performance of an algorithm can be evaluated by using Big-O notation based on the size of the input data. Both Array Queue and Circular Array Queue are the linear data structures that implement a queue in which the Array Queue stores the elements in a standard array whereas the Circular Array Queue stores in a circular buffer. Big-O Notation can be used to find the execution time for both Array Queue and circular Array Queue.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
