Here are the class definitions of Node and List that impleme

Here are the class definitions of Node and List that implement a linked list. class Node {private Node next; private int key; Node (Node nxt, int keyValue);//constructor Node getNext(); int getKey(); void put(Next Node nxt);} class List {//assume the class does not use a dummy Node private Node head; List ();//constructor boolean exists(int ky);//returns true if v is in the list void insertAtHead(int ky);//inserts at the beginning of the list void insertAtTail(int ky);//inserts at the end of the list int removeFromHead ();//Returns -1 if the list is empty void delete(int ky)//delete the element or do nothing if v doesn\'t exist int removesmallest ();//removes the Node containing the smallest key//and returns that key. Returns -1 if the list is empty.//could be duplicate entries, so remove the first//int remove Largest ();//removes the Node containing the largest key//and returns that key. Returns -1 if the list is empty.//Could be duplicate entries, so remove the first int maxElement ();//calls the private version, doesn\'t delete the Node int sum ();//calls the private version int length ();//calls the private version private int maxElement (Node x); private int sum (Node x); private int length Node x);} Algorithm A has running time T_A(n) = 10^6 + 10^4 times n + 10^5 times n^2 and algorithm B has miming time T_B(n) = 3 times n^3, where n is the number of values of the algorithms processes. Give the \"big O\" equations for the running times and state which algorithm is fastest for large n.

Solution

Big-O notation is a way to express the efficiency of an algorithm. It measures the efficiency of an algorithm against the input size.It takes into account, \"how the execution time of a program scales with the input data\". This is very important line since we roughle estimate the time and not actually calculate the time.For example

O(N), O(2N), O(500N) all have same efficiency.Why? Because we are measuring the growth of time against the input size.

Now coming to your question

T_A(n)=10⁶+10⁴*n+10⁵*n² will be represented in Big O as

O(N²)

similarly

TB(n)=3*n³ will be represented as

O(N³)

For input size N algorithm A has faster running time than algorithm B. A grows by square of input size while B grows as cube of input size.