1) Which of the following are in O (n): a) n + lg n b) n...

Question

Question

1) Which of the following are in O (n): a) n + lg n b) n...

1) Which of the following are in O (n):

a) n + lg n b) n + 2n c) n + n2 d) 1000 n + 4500 lg n + 54 n

2) What is a stack? Give an ADT.

3) How would you implement the push method for a Stack implemented as a Linked List?

4) How would you implement the pop method for a Stack implemented as a Linked List?

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

1)
a) n + lg n = O(n)
b) n + 2n = O(2^n)
c) n + n2 = O(n^2)
d) 1000 n + 4500 lg n + 54 n = O(n)

so, a and d are in O(n)

Add a comment

Answer 2

Similar Homework Help Questions

1)Given a Stack implemented with a Linked List, and an O(1) implementation of push and pop,show...

1)Given a Stack implemented with a Linked List, and an O(1) implementation of push and pop,show the Linked List after the following commands are executed: Stack myStack = new Stack(); myStack.push(20); myStack.push(40); myStack.pop(); myStack.push(60); myStack.push(80); 2)If the same commands were used but the Stack was implemented with an Array with maximum size of 10, show what the array would look like after all these commands are executed. Assume O(1) implementation of push and pop here as well. 3)Given a Queue...
Name: Each question is worth 1 point. 20 1. In a linked-chain implementation of a Stack...

Name: Each question is worth 1 point. 20 1. In a linked-chain implementation of a Stack ADT, the performance of pushing an entry onto the stack is a. 0(2) b. О(n) С. 0(r) Answer: What is the entry returned by the peek method after the following stack operations. push(A), push(R), pop0. push(D), popO, push(L), pop0, pushJ), push(S), pop). pop 2. b.S c. L d. D Answer: n an efficient array-based chain implementation of a Stack ADT, the entry peek returns...
1. Which implementation would you use to implement very dense polynomials of degree up to 100....

1. Which implementation would you use to implement very dense polynomials of degree up to 100. (Array/Linked List) 2. Which implementation would you use on a stack that requires frequent operations of push and pop and whose size is guaranteed to stay below 50. (Array/Linked List)

» Part A: Stack Create a Stack struct that is a wrapper for your linked list o You should impleme...

Using C Please comment » Part A: Stack Create a Stack struct that is a wrapper for your linked list o You should implement the following functions that take a stack o void push(Stack * stack, int value) ● int pop(Stack * stack) Prompt the user to input 5 integers, and use the stack to reverse the integers Print the result to the screen. o o » Part B: Queue o Create a Queue struct that is a wrapper for...
JAVA PROGRAM: public class Stack { private DList mList; public Stack() { setList(new DList<>()); } private int indexOfTop() { return getList().isEmpty() ? -1 : getList().getSize() - 1; } public...

JAVA PROGRAM: public class Stack { private DList mList; public Stack() { setList(new DList<>()); } private int indexOfTop() { return getList().isEmpty() ? -1 : getList().getSize() - 1; } public E peek() { return getList().get(indexOfTop()); } public E pop() { return getList().remove(indexOfTop()); } public Stack push(E pData) { getList().append(pData); return this; } private DList getList() { return mList; } private void setList(DList pList) { mList = pList; } Q1 Because Stack encapsulates an instance variable which is of the class DList,...
1. Write a function using C++ which will determine the length of a circularly linked list....

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)?

Given a singly linked list contains 5 nodes, which simply shows as 5->4->3->2->1, what is the...

Given a singly linked list contains 5 nodes, which simply shows as 5->4->3->2->1, what is the value that you can find in the second node of the remaining list if the following statements are applied? Assume head reference refers the first node of the list. Node prev = head; Node curr = head. next; while(curr.next!=null) { if(prev.element > 3) { prev = curr; curr = curr.next; } else break; } head = prev.next; Question 3 options: 3 2 4 1...
Can you please help with the below? 1) Which of the following is true about using...

Can you please help with the below? 1) Which of the following is true about using a 2-3-4 tree? a. It is designed to minimize node visits while keeping to an O(log n) search performance b. It is designed to self-balance as new values are inserted into the tree c. As soon as a node becomes full, it performs the split routine d. None of the above 2) Which of the following is true about a binary search tree? a. ...
1. static int function(int n){ return n * function(n + 1); } If you call the...

1. static int function(int n){ return n * function(n + 1); } If you call the method function(2), the expected output is 3. True False 2. public void push(int new_data) { Node new_Node = new Node(new_data); new_Node.next = head; new_Node.prev = null; if (head != null) head.prev = new_Node; head = new_Node; } The code snippet depicts stack implementation True False 3. A ________ list is a linked data structure that consists of a set of sequentially linked records called...

1. a. Stack b. Queue c. Priority Queue d. List - (ADTs) Given the following steps: push(...

1. a. Stack b. Queue c. Priority Queue d. List - (ADTs) Given the following steps: push( "Jane" ); push( "Jess" ); push( "Jill" ); push( pop() ); push( "Jim" ); String name = pop(); push( peek() ); Write separate programs for each of the data structures Stack, Queue, PriorityQueue, and List. Use the appropriate push(), pop(), peek() for each of the respective ADT's. Use the Java class library of the ADT's as opposed to the author's implementation. What is in...

1) Which of the following are in O (n): a) n + lg n b) n...

Homework Answers

Add Answer to:
1) Which of the following are in O (n): a) n + lg n b) n...

Post as a guest

Earn Coins

1)Given a Stack implemented with a Linked List, and an O(1) implementation of push and pop,show...

Name: Each question is worth 1 point. 20 1. In a linked-chain implementation of a Stack...

1. Which implementation would you use to implement very dense polynomials of degree up to 100....

» Part A: Stack Create a Stack struct that is a wrapper for your linked list o You should impleme...

JAVA PROGRAM: public class Stack { private DList mList; public Stack() { setList(new DList<>()); } private int indexOfTop() { return getList().isEmpty() ? -1 : getList().getSize() - 1; } public...

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

Given a singly linked list contains 5 nodes, which simply shows as 5->4->3->2->1, what is the...

Can you please help with the below? 1) Which of the following is true about using...

1. static int function(int n){ return n * function(n + 1); } If you call the...

1. a. Stack b. Queue c. Priority Queue d. List - (ADTs) Given the following steps: push(...

1) Which of the following are in O (n): a) n + lg n b) n...

Homework Answers

Add Answer to: 1) Which of the following are in O (n): a) n + lg n b) n...

Post as a guest

Earn Coins

Add Answer to:
1) Which of the following are in O (n): a) n + lg n b) n...