Which of the following is not O(n2)?

S8 cOMPREHENSIVE VIVA ALGORITHM ANALYSIS AND DESIGN

Quiz
•
Computers
•
Professional Development
•
Hard

Arya S R
Used 1+ times
FREE Resource
25 questions
Show all answers
1.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
(1510) * n + 12099
n1.98
n3/(sqrt(n))
(220) * n
2.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Which of the following is not a backtracking algorithm?
Knight tour problem
N queen problem
Tower of hanoi
M coloring problem
3.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1 Which one of the following is false.
T(n) = O(n^2)
T(n) = (nLogn)
T(n) = (n^2)
T(n) = O(nLogn)
4.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?
O(n2log(n))
Theta(n2log(n))
Theta(n4)
Theta(n3)
5.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
248000
44000
19000
25000
6.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?
X[i, j] = X[i - 1, j] ∨ X[i, j -ai]
X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]
X[i, j] = X[i - 1, j] ∧ X[i, j - ai]
X[i, j] = X[i - 1, j] ∧ X[i, j - ai
7.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
θ(n)
θ(logn)
θ(log*n)
θ(1)
Create a free account and access millions of resources
Similar Resources on Quizizz
20 questions
1ºDAM/DAW - Lenguajes de Marcas - UD2-3-9 - Prof. C. Boni

Quiz
•
University - Professi...
30 questions
Typing words and symbols on keyboard (1)

Quiz
•
KG - Professional Dev...
20 questions
KEYBOARDING QUIZ

Quiz
•
Professional Development
20 questions
EVALUACION 1 DE TALLER (jueves)

Quiz
•
Professional Development
21 questions
Computer

Quiz
•
6th Grade - Professio...
20 questions
Module 2 Review

Quiz
•
Professional Development
28 questions
Enderman Language

Quiz
•
KG - Professional Dev...
30 questions
Algorithm - Complexity

Quiz
•
University - Professi...
Popular Resources on Quizizz
15 questions
Multiplication Facts

Quiz
•
4th Grade
25 questions
SS Combined Advisory Quiz

Quiz
•
6th - 8th Grade
40 questions
Week 4 Student In Class Practice Set

Quiz
•
9th - 12th Grade
40 questions
SOL: ILE DNA Tech, Gen, Evol 2025

Quiz
•
9th - 12th Grade
20 questions
NC Universities (R2H)

Quiz
•
9th - 12th Grade
15 questions
June Review Quiz

Quiz
•
Professional Development
20 questions
Congruent and Similar Triangles

Quiz
•
8th Grade
25 questions
Triangle Inequalities

Quiz
•
10th - 12th Grade