‘O’ Big O Notation

O

Big O notation is used to  classify algorithms by how they respond. Simply it is used to calculate the complexity of a program.
It is normal shown by O(n). ‘n’ is the time of the program will run. Some times it becomes n*n because some times same loop run again and again. There can be n/2 also. It all depends on how the code will execute.
Constants are taken as 1 and in the end 1 is deleted because it want harm the complexity calculations.

This is a simple example from the course work I did

public void deleteNode(int v) { //Method where a node is deleted through      a linked list

Listnew cur = head;

while (cur != null) {

cur.list.deleteNode(v);

cur = cur.nextNode;

}

}

public void deleteNode(int v) { // Delete a value from the list

int count = 0;

Node prev;

Node cur;

Node tmpHead = new Node();

tmpHead.next = head;

prev = cur = tmpHead;

cur = cur.next;

while (cur != null) {

if (cur.value == v && count == 0) {

cur = cur.next;

prev = cur;

tmpHead.next = cur;

} else if (cur.value == v) {

cur = cur.next;

prev.next = cur;

} else {

cur = cur.next;

prev = prev.next;

}

count++;

head = tmpHead.next;

}

}

This is the way to calculate the complexity using Big O notation.

while (cur != null) {   ——-(n)

cur.list.deleteNode(v);

cur = cur.nextNode;

}
If we take this loop executes n times then the rest of the code underneath it executes n times. So the whole Big O notation is (n+n*n)
So running time Big O notation is O(n*n).

Also in the method delete a node. In that class there is a while loop also.
while (cur != null) {       ——- (n)

if (cur.value == v && count == 0) {  (1*n+1*n+1*n)

cur = cur.next;       ——-(1*n)

prev = cur;

tmpHead.next = cur;

} else if (cur.value == v) { ——- (n*1)

cur = cur.next;

prev.next = cur;

} else {         ——-  (n*1)

cur = cur.next;

prev = prev.next;

}

count++;           ——- (n*1)

head = tmpHead.next;     ——- (n*1)

}
This also run n times because it is called by the earlier method. If conditions are run 1 time for each occurrence so we take if and else as 1. That condition becomes ‘n’ and else also becomes ‘n’. So in this method also Big O is O(n). Complete delete Operation Big O notation becomes (n+n*n).

So the Big O notation for the search operation for a number of this data structure is O(n*n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s