Question

1. Write a function using C++ which will determine the length of a circularly linked list.

2. Determine if the expression is true or false. Give a reason for your conclusion.

(a) Is n lg(n + 17) ∈ O(n 2 )?

(b) Is n 2 ∈ O(n √ n)?

(c) Is 3n ∈ O(n 3 )?

(d) Is 2n ∈ O(3n )?

(e) Is lg(lg(lg(n))) ∈ O(n)?

Answer 1

The basic structure of the program will fist have to make a circulay linked list

struct N {

    int data;

    struct N* next;

};

Once we have this Structure we'll write a loop to create a linked list.

The below function will add nodes to the circular linked list the process to do that is

Step 1: Create a Node from Structure

Step 2: Make the last element to point it

Step 3: Put the link of the next node in the new one as the header of the linked list to make it circular

void push(struct N** head, int data)

{

    struct N* ptr1 = (struct N*)malloc(sizeof(struct N));

    struct N* tmp = *head;

    ptr1->data = data;

    ptr1->next = *head_ref;

if (*head != NULL) {

        while (tmp->next != *head)

            tmp = tmp->next;

        tmp->next = ptr1;

    } else

        ptr1->next = ptr1;

    *head = ptr1;

} The input needs the link of the head and the data in the node to so the operations as shown in the code above.

Now to count the number of nodes or what we can call as length of the list.

int length(struct N* head)

{

    struct N* tmp = head;

    int result = 0;

    if (head != NULL) {

do{

            tmp = tmp->next;

            result++;

        } while (tmp != head);

}

    return result;

}

Now in the mail program just calling length(head) where head is point of the linked list we want to find the length of.

We are instructed to solve only one problem at a time on the platform.

If any doubts in the solution do put in comments