Time Complexity MCQ Quiz - Objective Question with Answer for Time Complexity - Download Free PDF

The correct answer is NP-Hard.

Key Points

• Assuming P ≠ NP implies that problems in P are not the same as NP-Complete problems.
• NP-Complete problems are the hardest problems in NP, in the sense that if any NP-Complete problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time.
• If a problem is both in NP-Complete and in P, it would imply P = NP, which contradicts our assumption.
• Therefore, the intersection of NP-Complete and P must be empty under the assumption that P ≠ NP.
• So, NP-Complete ∩ P = ∅ (the empty set).

Additional Information

• NP-Hard problems are at least as hard as the hardest problems in NP, but they do not necessarily have to be in NP.
• If a problem is NP-Hard, it means solving it in polynomial time would allow all NP problems to be solved in polynomial time.
• The concept of NP-Hard is crucial in the study of computational complexity theory, as it helps in understanding the limits of efficient computation.
• In practical terms, knowing a problem is NP-Hard helps in setting realistic expectations for finding efficient algorithms for it.

The correct answer is (A) - (III), (B) - (I), (C) - (II), (D) - (IV)

• A (Bellman-Ford Algorithm) → III (O(nm))
• B (Dijkstra Algorithm) → I (O(|V|²))
• C (Prim's Algorithm) → II (O((V + E) log V))
• D (Topological Sorting) → IV (O(n + m)) 

Key Points

1. Bellman-Ford Algorithm → O(nm) Iterates |V| - 1 times over E edges, giving O(VE), which is O(nm) in dense graphs.

2. Dijkstra’s Algorithm → O(|V|²) Using an adjacency matrix, it scans all vertices, leading to O(V²) time complexity.

3. Prim’s Algorithm → O((V + E) log V) Uses a priority queue (min-heap) with adjacency list, giving O((V + E) log V).

4. Topological Sorting → O(n + m) Uses DFS or Kahn's algorithm, iterating over V vertices and E edges, resulting in O(V + E)

Important Points

• Bellman-Ford algorithm is used for finding the shortest paths from a single source vertex to all other vertices in a weighted graph.
• Dijkstra's algorithm is also used for finding the shortest path in a weighted graph but does not work with negative weight edges.
• Prim's algorithm is used to find the minimum spanning tree of a weighted graph.
• Topological sorting is used for ordering the vertices of a directed acyclic graph (DAG).

Additional Information

• The Bellman-Ford algorithm can handle negative weights, unlike Dijkstra's algorithm.
• Prim's algorithm and Dijkstra's algorithm have similar structures, but they solve different problems.
• Topological sorting is crucial for tasks scheduling, such as in project management.

The correct answer is O(n2)

Explanation:

Total number of unsorted arrays is n and each array contain n distinct element.

Time complexity to find median from an array is O(n).

Since there is ‘n’ such array. Therefore, total time complexity to find medians of all arrays is O(n2)

Store the ‘n’ medians in an array. Find the medians of the array with time complexity of 0(n)

Total Time complexity:

T(n) = O(n2) + O(n) = O(n2)

The correct answer is Shortest Path Problem.

Key Points

• The Shortest Path Problem is a classic problem in graph theory that involves finding the shortest path between two vertices in a weighted graph.
  • One common algorithm used to solve this problem is Dijkstra's algorithm, which efficiently finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.
  • Another well-known algorithm is the Bellman-Ford algorithm, which can handle graphs with negative edge weights and detect negative cycles.
  • The Shortest Path Problem is not considered an NP-Complete problem because it can be solved in polynomial time using these algorithms.
  • In contrast, NP-Complete problems, such as the Traveling Salesman Problem and the Boolean Satisfiability Problem, are known to be computationally difficult and no polynomial-time solution is known for them.

Additional Information

• NP-Complete problems are a class of problems for which no known polynomial-time algorithms exist, and they are believed to be inherently difficult to solve.
• Other well-known NP-Complete problems include the Knapsack Problem, the Hamiltonian Cycle Problem, and the Vertex Cover Problem.
• The concept of NP-Completeness is central to the field of computational complexity theory, which studies the inherent difficulty of computational problems and the resources required to solve them.
• Proving that a problem is NP-Complete involves demonstrating that it is both in NP (nondeterministic polynomial time) and that every problem in NP can be reduced to it in polynomial time.

The correct option is (3)

Explanation:- 

The null case does not exist while calculating time complexity.

Time complexity:- The time complexity, measured in the number of comparisons. In other words, the time complexity is essential, efficiency, or how long a program function takes to process a given input.

Additional InformationAverage case:- In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource used by the algorithm, averaged over all possible inputs.

Best case:- The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be 0(1). Most of the time, we do worst-case analysis to analyze algorithms.

Worst case:- In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed.

\(T\left( n \right) = 2\;T\left( {\sqrt n } \right) + 1\)

Put n= 2^m, m = log₂n

\(T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1\)

\(Put\;T\left( {{2^m}} \right) = S\left( m \right)\)

\(S\left( m \right) = 2\;S\;\left( {\frac{m}{2}} \right) + 1\)

Now, calculate \({n^{log_b^a}}\)

\({m^{log_b^a}} = m\)

S (m) = m + 1

S(m) = m

Put the value of m 

Therefore, T(n) in terms of Θ notation is Θ (logn).

\(\begin{array}{l} \therefore p\; = \;\log n,\;q\; = \;\log p\; = \;\log \left( {\log n} \right)\\ \therefore q\; = \;n.\log \left( {\log n} \right) \end{array}\)

\(T\left( n \right) = 4T\left( {√ n } \right) + lo{g^2}n\)

Consider n = 2^m

m = log₂n

n = 2m

Taking square root

√n = 2m/2

T(2^m) = 4T(2^m/2) + m²

Put S(m) = T (2^m/2)

S(m) = 4 S(m/2) + m²

Comparing with

T(m) = a T(m/k) + cmk

a = 4, b = 2, k = 2

a = b^k = 4

Now use master’s theorem :

T(m) = O(mklog m)

So, Time complexity will be O(m²log m)

Put the value of m

Time complexity will be :  O (log²n log (logn))

We have to check how many times inner loop will be executed here.

For i=1,

j will run 1 + 2 + 3 + …………. (n times)

For i=2

j will run for 1,3,5, 7, 9, 11,………..(n/2 times)

For i=3

j will run for 1,4,7,10, 13…………… (n/3 times)

So, in this way,

\(T\left( n \right) = n + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5} + \frac{n}{6} \ldots + \frac{n}{n}\)

\(= n\left( {1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \ldots + \frac{1}{n}} \right)\;\)

So, Time complexity of given program = Θ (n log n)

Concept:

Sin function value ranges from -1 to + 1. (-1, 0, 1)

Explanation:

Case 1: when sin(n) is -1,

g(n) = n^{(1 - 1)} = n⁰ = 1

so, for this case f(n) > g(n) i.e. g(n) = O (f(n))

So, statement 1 is incorrect.

Case 2: when sin(n) is +1,

g(n) = n^{(1 + 1)} = n²

so, for this case f(n) < g(n) i.e. f(n) = O(g(n))

but for this, second statement i.e. f(n) = Ω(g(n)) is incorrect.

Both statements are not true for all values of sin(n).

During transpose of the matrix, it is partitioned into 4 submatrices of size N/2.

If n = 1, then T(1) = 1

Else T₁(n) = 4T₁(N/2) + O(1)       ----- (1)

Solving equation 1 by master’s theorem:

\({n^{log_b^a}} = \;{n^{log_2^4}} = {n^2}\), here a= 4 and b = 2

So, T₁(n) = O(N²)

But the algorithm is multithreaded, and transposing is going in parallel. And we solved one subproblem already.

So, T_n(N) = T_n(N/2) + O(1)

T_n(N) becomes O(log N)

asymptotic parallelism of the algorithm:

T₁/T_∞ or θ (N²/lg N)

To find the worst-case time complexity of the function.

Worst case happens in case of recursive. So, find out the recursive calls on the longer route.

There are 5 such recursive calls to A (n/2).

So, recurrence relation will become like:

A (n) = 5A (n/2) + O(1)

where O(1) is constant

By using master’s theorem,

a = 5, b =2

\({\rm{O}}\left( {{{\rm{n}}^{{{\log }_2}5}}} \right) = {\rm{\;O}}({{\rm{n}}^{2.32}})\)

\({\rm{O}}({{\rm{n}}^{\rm{\alpha }}}) = {\rm{O}}({{\rm{n}}^{2.32}}){\rm{\;}}\)

α = 2.32

Given values are: 10 (a constant value)

√n (square root of a variable n which can take any value) n (a variable) log₂n (logarithmic)

\(\frac{100}{n}\) (it divides 100 by a variable)

As we know that constant is smaller than a variable in case of asymptotic complexity because a variable can take any value smaller or larger. But when we compare 10 with \(\frac{100}{n}\), as 100 is divisible by n and if n goes to infinite than this value will become zero. So, \(\frac{100}{n}\) is smaller than 10.

In the case of log₂n growth rate is logarithmic which is smaller than linear growth.

Comparison between √n and n. Linear growth in case of n, it is larger than √n.

So, complete order is: \(\frac{100}{n}\) < 10 < log₂ n < √n < n                                                                                        

Alternated method:

Take n = 2¹⁰²⁴

10, \(2^{\frac{1024}{2}}\), \(\frac{100}{2^{1024}}\), log₂(2¹⁰²⁴), 2¹⁰²⁴

10, 2⁵¹², \(\frac{100}{2^{1024}}\), 1024 × log₂2, 2¹⁰²⁴

10, 2⁵¹², \(\frac{100}{2^{1024}}\), 1024, 2¹⁰²⁴

In terms of increasing order:

100/(2¹⁰²⁴) < 10 < 1024 < 2⁵¹²< 2¹⁰²⁴

Answer: Option 4

Explanation:

T(n) = T(n/2) + T(2n/5) + 7n

T(n) = \(7n\left( {1 + \;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + \;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_2}n}}} \right)\) ( for left most subtree base of log is 2 But for rightmost subtree base will be (5/2))

For rightmost subtree:
T(n) =  \(7n\left( {1 + \;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + \;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_{5/2}}n}}} \right)\)

T(n) = 7n(1-n^{\({\log _2}0.9\)})

T(n) = O(n) 

and similarly for right most subtree 

T(n) = Ω(n) 

hence T(n) = θ(n) 

The correct answer is option 3.

Explanation:

Recurrence relation: T(n) = 7T(n/7) + n

Comparing with T(n) = aT(n/b) + θ(n^k log^pn)

a = 7, b = 7, k = 1, p = 0

Using Master's Theorem,

Since a = b^k and p > -1,

T(n) = O(nlog(n))