Running time of linkedlist and sorted arraylist BIG OMEGA NOTATION .Running time

Question

Running time of linkedlist and sorted arraylist BIG OMEGA NOTATION

.Running time of LinkedList and Sorted ArrayList functions. Questions (refers to both Linked list without a tail and Sorted Array List, so you need to have 4 answers. PLEASE PAY ATTENTION!! I DO NOT NEED THE CODE, I just need the 2 questions to be answered EXACTLY LIKE the examples given in the bottom of the question.

1) Reversing the list (content of each node).

Linked List:

Sorted Array:

2) Removing a value at a given index.

Linked List:

Sorted Array:

Please give your answer like the answers below. Example Question: Adding a value to the beginning of the linked list. Example Answer: Running time: (1). You have a pointer to the head node in the list, so adding an element involves creating a new node (which is not dependent on the length of the list), setting the links in the new node, and changing the values of the head references. This takes somewhere around 10 steps to perform, and 10=(1). Example Question: Adding a value to the beginning of the array list. Example Answer: Running time: (n). You have to move everything over one cell to create a room for a new element. It will be done using a for loop that iterates through all elements. Since there are n elements in the list, it takes (n) to add a new element to the beginning of the array list.

Explanation / Answer

Deleting a number at given index in Array

after at given index shift all the element by one position left so that number is overwrriten so basically its goes deleted.or manually delete content of that location then do shift operation

suppose total number in the arrayList is n and given index is i. so its require (n-i) element shifted one position left(after ith index) and iterate through loop.

(n-i)=O(n) i<n.

somewhere you find it can be done in order O(1) so means they not shifted ,elements left by one position. just delete content and leave created vaccume in the arraylist.

Deleting a given node in linked list

Deletion of head node is done in O(1).

but if we need to delete some other position ,then we need to iterate through loop to reach that node that why its require O(n).

code for deletion a node .down

void deleteNode( Node * node )

{ Node * temp = node->next;

node->data = node->next->data;

node->next = temp->next;

free(temp);

}

Reversing linked list

There are many methods for reversing Linked List

1. Traverse linked list head to tail and push each element into stack so head goes on the bottom last one comes upper and now popup one by one and creates linked list again this operation require loop ,so time complexity O(n).

another method

2. keep three pointer with you,let say currentnode,nextnode and previousnode

method is simple goes iterate through loop set first node to null and reverse the link of all other node.

example: 1->2->3->4->null

initialise previousnode and nextnode to null

currentnode to 1 means to the head of linked list

now follow the procedure :

while(currentnode!=null)

{ nextnode=currentnode.next;   

currentnode.next=previousnode;
previousnode=currentnode;
currentnode=nextnode;
}

head=previosnode;

//its require traversing through loop so time complexity is O(n) but in previous case space complexity is O(n) and in this case space compxity O(1).

Reversing Sorted arrayList

you just need a temporary variable for the purpose of swaping two element

iterate a loop 0 to n/2

pseudo code

for i=0 to n/2

temp=array[n-1-i];

array[n-1-i]=array[i];

array[i]=temp;

repeat

example : 1 2 3 4 5 in each pass through loop two element are swaped

5 2 3 4 1

5 4 3 2 1   

it iterate through loop n/2 times

n/2=O(n).

if you have doubt please comment

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.