Question 1 5 out of 5 points An algorithm is a set of steps to solve a problem.

Question

Question 1

5 out of 5 points

An algorithm is a set of steps to solve a problem.

Question 2

5 out of 5 points

Running Time important factor in choosing an algorithm.

Question 3

5 out of 5 points

T(N) = O(f(N)) means T(N) >= c*f(N) for N >= 0

Question 4

5 out of 5 points

If T1(N) = O(f(N)) and T2(N) = O(g(N)), then T1(N) + T2(N) = O(f(N) + g(N))

Question 5

5 out of 5 points

The choice of an algorithm matters most when the input size is small.

Question 6

0 out of 5 points

An algorithm which repeatedly reduces a problem by a fraction in constant time is O(log(N))

Question 7

0 out of 5 points

A worst case running time analysis tells us the upper limit of how poor the performance can be.

Question 8

0 out of 5 points

The stack operations push and pop can have O(1) running time

Question 9

0 out of 5 points

If a linked list is doubly linked, it means the last node points to the first node

Question 10

0 out of 5 points

An array supports insertion and removal of items within the list in constant time

Question 11

5 out of 5 points

Finding a node in a linked list requires O(N) running time.

Question 12

5 out of 5 points

Match on worst case running time

Big O

Theta

Omega

Little o

Question 13

0 out of 5 points

What is the worst case Big-O running time of the following pseudocode?

for (i=0; i<n; i++) {
   m=n
   while (m>0)
      m = m/2    //integer division
}

Question 14

0 out of 5 points

What is the worst case Big-O running time of the following pseudocode if list is a LinkedList?

for (i=0; i<n; i++) {
   list.add(0, i); // add value i at front of the list
   x = list.get(i); // gets value at index position
   print(x)
}

Question 15

0 out of 5 points

What is the worst-case Big-O running time of the following pseudocode?

for (i=0; i<n; i++) {
if (a == b)
for (k=0; k<n; k++) {
print i, k;
}
else
print i;
}

Question 16

0 out of 5 points

What is the worst-case Big-O running time of the following pseudocode?

while (n>1) {
n = n/2
print()
}

Question 17

0 out of 5 points

What is the worst-case Big-O running time of the following pseudocode?

for (i=1; i<=n; i++)
   for (j=1; j<=n; j=i+j)
       print()

Question 18

5 out of 5 points

What is the worst-case Big-O running time of the following pseudocode?

T(n) = n + T(n-1) n>1
       = 1                n=1

Question 19

0 out of 5 points

What is the worst-case Big-O running time of the following pseudocode?

T(n) = 2T(n/2) + C   n>1
       = C                   n=1

Question 20

0 out of 5 points

What is the slowest? answer the letter of the function

f = 2^N   g = Nlog(N)   h = N^log(N)

An algorithm is a set of steps to solve a problem.

Explanation / Answer

Answer 19 :

T(n) = 2T(n/2) + C , n > 1 ------------ > (1)

By Substitution , we have

T(n/2) = 2T(n/4) + C

Substitute the value of T(n/2) in 1 , we get

T(n) = 2( 2T(n/4) + C ) + C

=> T(n) = 2^2T(n/2^2) + 2c

.

.

.

T(n) = 2^k T(n/2^k) + k*C

Let 2^k = n

logn = k

T(n) = 2^logn T(n/2^logn) + logn *C

T(n) = nT(1) + logn*C

=> T(n) = n + logn [ C is a constant ]

=> T(n) = O(n)

DEAR YOU ARE REQUESTED TO PLEASE RATE THE ANSWER IF HELPS ELSE LET ME KNOW YOUR DOUBT.

KINDLY POST SEPARATELY AS WE ARE RESTRICTED TO ANSWER MORE THAN ONE QUESTION FROM MULTIPLE POSTED QUESTIONS.

THANK YOU!!!

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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