Big O notation
I've completed the methods of three seperate programs below. In learning about Big O notation, I have to identify which formula each method would use. The concept of Big O is quite confusing to me, but i've given a go at it, and was wondering if anyone could provide some correction/suggestions/advice. Each code block is an individual method, and i've put my answer, as well as why I chose that answer, before each block.
Most importantly I need to see if my answers are way off- but also any tips onto what to look for in code to decide which formula to use would really help.
It looks like a lot of code, but in reality many of the methods are similar and quite short. Any help is greatly appreciated.
Implementing a Resizable Stack
O(n) because it goes trough and array, and depends on the number (n) of things to do.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(n) goes through the array so it depends only on n items.
O(n) because it goes trough and array, and depends on the number (n) of things to do.
O(n) because it goes trough and array, and depends on the number (n) of things to do.
Implementing a Circular Queue
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(n) - this depends on n because it is a loop and therefor depends on the number of items. It is two for loops but they are NOT nested so it isn't O(n^2) ( i.e. n squared)
Array Implementation of an Ordered List
O(n) This one is more complicated- and I'm not even sure but i'm going to venture a guess that its O(n) based on the same answer I gave for the previous one.
O(n) - again- i'm not even too sure one this one
Most importantly I need to see if my answers are way off- but also any tips onto what to look for in code to decide which formula to use would really help.
It looks like a lot of code, but in reality many of the methods are similar and quite short. Any help is greatly appreciated.
Implementing a Resizable Stack
O(n) because it goes trough and array, and depends on the number (n) of things to do.
Code: Select all
public void setCapacity (int capacity) throws IllegalStateException
Object [] newArray = new Object [capacity];
for (int i=0; i<top ;i++){
newArray[i] = array[i];
}
array = newArray;
}
Object [] newArray = new Object [capacity];
for (int i=0; i<top ;i++){
newArray[i] = array[i];
}
array = newArray;
}
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(n) goes through the array so it depends only on n items.
Code: Select all
public void trim () {
if(top > 0){
Object [] newArray = new Object [top];
for (int i=0; i<top ;i++){
newArray[i] = array[i];
}
array = newArray;
}
else{
Object[] newArray = new Object[1];
array = newArray;
}
}
if(top > 0){
Object [] newArray = new Object [top];
for (int i=0; i<top ;i++){
newArray[i] = array[i];
}
array = newArray;
}
else{
Object[] newArray = new Object[1];
array = newArray;
}
}
O(n) because it goes trough and array, and depends on the number (n) of things to do.
Code: Select all
public void clear () {
for (int i=0; i<array.length; i++){
array[i]=null;
top=0;
}
}
for (int i=0; i<array.length; i++){
array[i]=null;
top=0;
}
}
O(n) because it goes trough and array, and depends on the number (n) of things to do.
Code: Select all
public void reset () {
array = new Object [initCapacity];
for (int i=0;i<array.length;i++)
array[i]=null;
top=0;
}
array = new Object [initCapacity];
for (int i=0;i<array.length;i++)
array[i]=null;
top=0;
}
Implementing a Circular Queue
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
Code: Select all
public void add (Object item) {
if (isFull()){
addToCapacity(3);
}
array[rear] = item;
rear = (rear + 1) % array.length;
itemCount++;
}
if (isFull()){
addToCapacity(3);
}
array[rear] = item;
rear = (rear + 1) % array.length;
itemCount++;
}
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
Code: Select all
public Object remove () throws IllegalStateException {
Object hold = array[front];
front = (front + 1) % array.length;
itemCount--;
return hold;
}
Object hold = array[front];
front = (front + 1) % array.length;
itemCount--;
return hold;
}
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
Code: Select all
public void reset () {
array = new Object[initCapacity];
itemCount=0;
front=0;
rear=0;
}
array = new Object[initCapacity];
itemCount=0;
front=0;
rear=0;
}
O(n) - this depends on n because it is a loop and therefor depends on the number of items. It is two for loops but they are NOT nested so it isn't O(n^2) ( i.e. n squared)
Code: Select all
private void addToCapacity (int increment) throws IllegalStateException {
Object [] newArray = new Object [array.length+increment];
for (int i=0; i<rear ;i++){
newArray[i] = array[i];
}
for (int i=front; i<array.length ;i++){
newArray[i+increment] = array[i];
}
front = front + increment;
array = newArray;
}
Object [] newArray = new Object [array.length+increment];
for (int i=0; i<rear ;i++){
newArray[i] = array[i];
}
for (int i=front; i<array.length ;i++){
newArray[i+increment] = array[i];
}
front = front + increment;
array = newArray;
}
Array Implementation of an Ordered List
O(n) This one is more complicated- and I'm not even sure but i'm going to venture a guess that its O(n) based on the same answer I gave for the previous one.
Code: Select all
public void insert (String value) {
//search array from index 0 upwards
int i = 0;
for (i = 0; i < itemCount; i++){
Item curItem = (Item)array[i];
String curValue = curItem.getValue();
int result = value.compareTo(curValue);
if (result == 0) {
curItem.incOccurrences();
return;
}
else if (result < 0){
break;
}
}
// make room
if (itemCount == array.length){
setCapacity(itemCount + 1);
}
for (int j = itemCount; j > i; j--){
array[j] = array[j-1];
}
array[i] = new Item(value);
itemCount++;
}
//search array from index 0 upwards
int i = 0;
for (i = 0; i < itemCount; i++){
Item curItem = (Item)array[i];
String curValue = curItem.getValue();
int result = value.compareTo(curValue);
if (result == 0) {
curItem.incOccurrences();
return;
}
else if (result < 0){
break;
}
}
// make room
if (itemCount == array.length){
setCapacity(itemCount + 1);
}
for (int j = itemCount; j > i; j--){
array[j] = array[j-1];
}
array[i] = new Item(value);
itemCount++;
}
O(n) - again- i'm not even too sure one this one
Code: Select all
public boolean remove (String value) {
//search array from index 0 upwards
int i = 0;
for (i = 0; i < itemCount; i++){
Item curItem = (Item)array[i];
String curValue = curItem.getValue();
int result = value.compareTo(curValue);
// if theres more than one, decrement
if (result == 0) {
curItem.decOccurrences();
// if there is only one, remove item and fill hole
if (curItem.getOccurrences() == 0){
for (int j = i; j<itemCount - 1; j++){
array[j] = array [j+1];
}
itemCount --;
}
return true;
}
else if (result < 0){
return false;
}
}
return false;
}
//search array from index 0 upwards
int i = 0;
for (i = 0; i < itemCount; i++){
Item curItem = (Item)array[i];
String curValue = curItem.getValue();
int result = value.compareTo(curValue);
// if theres more than one, decrement
if (result == 0) {
curItem.decOccurrences();
// if there is only one, remove item and fill hole
if (curItem.getOccurrences() == 0){
for (int j = i; j<itemCount - 1; j++){
array[j] = array [j+1];
}
itemCount --;
}
return true;
}
else if (result < 0){
return false;
}
}
return false;
}
- Anonymous
- Bot


- Joined: 25 Feb 2008
- Posts: ?
- Loc: Ozzuland
- Status: Online
March 16th, 2005, 7:04 pm
Well, in the first loop, the limit is itemCount.
In the second one, the limit is (itemCount -1).
They're two different values, although being very close to eachother.
The 'n' in O(n) would represent (itemCount * (itemCount -1)). If you start using a constant, like in O(n^2), you would have to have the same two values: (itemCount *itemCount ). Not necessarily the same variables, but the same values.
Torsten.
In the second one, the limit is (itemCount -1).
They're two different values, although being very close to eachother.
The 'n' in O(n) would represent (itemCount * (itemCount -1)). If you start using a constant, like in O(n^2), you would have to have the same two values: (itemCount *itemCount ). Not necessarily the same variables, but the same values.
Torsten.
- Mas Sehguh
- Mastermind


- Joined: 07 Aug 2004
- Posts: 1854
- Status: Offline
susancbk wrote:
The concept of Big O is quite confusing to me, but i've given a go at it, and was wondering if anyone could provide some correction/suggestions/advice.
Well, if you use a variable named n, you must explain what n actually means. Because some of these algorithms don't involve a value known as "n."
Technically, Big-O notation simply represents a set of functions -- the set of functions which grow at a slower or equal pace as the given function. When we say an algorithm runs in O(n^2) time, we mean that the amount of time it takes for the algorithm to run grows at a slower or equal pace as the function f(n) = n^2. "Growing at the same pace" means that as n grows really large, the ratio T(n)/(n^2 (where T(n) is the runtime for an input of size n) will either equal a constant number, like 3, or 20.5, or 0.2. "Growing at a slower pace" means that the ratio will get closer and closer to zero. Maybe this is redundant, but I can't be sure how well this has been explained.
susancbk wrote:
O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.
Code: Select all
public void add (Object item) {
if (isFull()){
addToCapacity(3);
}
array[rear] = item;
rear = (rear + 1) % array.length;
itemCount++;
}
if (isFull()){
addToCapacity(3);
}
array[rear] = item;
rear = (rear + 1) % array.length;
itemCount++;
}
This is not the case. You have to be careful. I annotated your function below:
Code: Select all
public void add (Object item) {
if (isFull()){
// Testing isFull() takes O(1) operations.
addToCapacity(3); // takes O(n) operations.
}
array[rear] = item; // This assignment takes O(1) operations
rear = (rear + 1) % array.length; // O(1) operations
itemCount++; // O(1) operations
}
if (isFull()){
// Testing isFull() takes O(1) operations.
addToCapacity(3); // takes O(n) operations.
}
array[rear] = item; // This assignment takes O(1) operations
rear = (rear + 1) % array.length; // O(1) operations
itemCount++; // O(1) operations
}
So most of the operations take O(1) runtime -- they run in a fixed amount of time. If all of them did, then the function would run in O(1) time, since 1+1+1+1+1 is 5, which is just a multiple of 1. But the addToCapacity function doesn't. The addToCapacity function takes O(n) operations. And 1+1+1+1+1+n runtime is O(n).
So the amount of time it takes to run the function, in the worst case, will be O(n).
When you analyse the runtime of an algorithm, you can't just look for for loops, you need to analyse the runtime line-by-line, and combine the parts together. When you have a for loop, figure out how much time the block will take to run, and then ask, "how many times will this block be called?", and multiply.
By the way, instead of adding 3 to the capacity, it is better to double the capacity, unless the capacity is zero, in which case make it equal to 1. If you add 3, you'll have to do a whole number of recopyings of the array. If you double the capacity, you'll have to do less recopying, in case somebody decides to add elements with
Putting objects on the end of an array or vector over and over again is a common practice.
If you add 3 to the length each time, you'll need to recopy a number of elements equal to 3 + 6 + 9 + 12 + ... + 999, which is equal to 166833 copy operations. If you double the length each time, you'd have to only recopy objects 1 + 2 + 4 + 8 + 16 + ... + 512 times, which is equal to 1023.
Page 1 of 1
To Reply to this topic you need LOGIN or REGISTER. It is free.
Post Information
- Total Posts in this topic: 5 posts
- Moderator: Moderator Team
- Users browsing this forum: No registered users and 102 guests
- You cannot post new topics in this forum
- You cannot reply to topics in this forum
- You cannot edit your posts in this forum
- You cannot delete your posts in this forum
- You cannot post attachments in this forum



