Asymptotic Worst Case Time and Time Complexity MCQ Quiz - Objective Question with Answer for Asymptotic Worst Case Time and Time Complexity - Download Free PDF

Correct Answer: Option 2) ∅

Key Points:

• NP-Complete problems are those that are:
  • In NP (verifiable in polynomial time), and
  • As hard as any problem in NP (i.e., every NP problem reduces to it in polynomial time).
• If a problem is both in P and NP-Complete, then all NP problems can be solved in polynomial time, i.e., P = NP.
• But it is given that P ≠ NP, so no NP-Complete problem can be in P.

Therefore, the intersection of P and NP-Complete is empty (∅).

Additional Information:

• NP-Hard: Includes problems at least as hard as NP problems but not necessarily in NP (not even decidable).
• P: Problems solvable in polynomial time.
• NP: Problems whose solutions can be verified in polynomial time.
• NP-Complete: Subset of NP problems that are also NP-Hard.

Hence: If P ≠ NP, no NP-Complete problem lies in P ⇒ NP-Complete ∩ P = ∅

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 option 4.

Explanation: 

Here are some common Big O notations from the smallest to the largest complexity:

• O(1): Constant-time complexity. The running time is independent of the input size, it always takes the same time to compute.
• O(log n): Logarithmic time complexity. The running time grows logarithmically in proportion to the input size.
• O(n): Linear time complexity. The running time grows linearly with the size of the input.
• O(n log n): Log-linear or Linearithmic time complexity. Running time grows linearly and in the order of the logarithm of the size of the input.
• O(n^2): Quadratic time complexity. The running time is proportional to the square of the size of the input data.
• O(n^3): Cubic time complexity. The running time is proportional to the cube of the size of the input data.
• O(2^n): Exponential time complexity. The resources needed for algorithm execution double with each addition to the input data set.
• O(n!): Factorial time complexity. The running time grows in proportion to the factorial of the input size. This is typical of algorithms that solve problems by generating all possible combinations.

So when you say "all types of asymptotic complexity increasing order", we could be talking about a set of functions like:

• f1(n) = 1 (O(1))
• f2(n) = log n (O(log n))
• f3(n) = n (O(n))
• f4(n) = n log n (O(n log n))
• f5(n) = n^2 (O(n^2))
• f6(n) = n^3 (O(n^3))
• f7(n) = 2^n (O(2^n))
• f8(n) = n! (O(n!))

So, according to above explanation:

•  f1(n) = 2ⁿ
•  f2(n) = n^3/2
•  f3(n) = n log n 
•  f4(n) = n^{log n}

The functions in ascending order: n log n  <  n^3/2 < n^{log n}   <   2ⁿ

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.

\(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).

Answer: Option 1

Explanation: 

f(n) =  n + module(n-1);  / since return (n + module(n-1));

Here recurrence relation will be

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

≡ T(n-2) + c + c

≡ T(n-3) + 3c

≡ T(n-k) + kc

when n-k = 1 ; k = n-1 and T(1) = 1

≡ T(1) + (n-1)c

≡ (n-1)c

≡ O(n) 

Hence Option 1 is correct answer.

Here some of you might have cam up with recurrence relation T(n) = T(n-1) + n, which is incorrect because in function n is just a variable it will have a constant value which will get added to call return value and In recurrence variable n indicate cost.  

\({\rm{T}}\left( {\rm{n}} \right) = 2{\rm{T}}\left( {\frac{{\rm{n}}}{2}} \right) + \log {\rm{n}}\)

Comparing with:

\({\rm{T}}\left( {\rm{n}} \right) = {\rm{aT}}\left( {\frac{{\rm{n}}}{{\rm{b}}}} \right) + f\left( n \right)\)

a = 2, b = 2, f(n) = log n

\({n^{{{\log }_2}2}} = n\) > f(n)

By Master’s theorem

\(T\left( {\rm{n}} \right) = {\rm{O}}\left( {\rm{n}} \right)\)

\(\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

The correct answer is Space efficiency and Time efficiency.

Key Points

• In computer science, algorithmic efficiency is a property of an algorithm that relates to the number of computational resources used by the algorithm.
• An algorithm must be analyzed to determine its resource usage, and the efficiency of an algorithm can be measured based on the usage of different resources. 
• Two areas are important for performance:
  • Space efficiency - a measure of the amount of memory needed for an algorithm to execute.
  • Time efficiency - a measure of the amount of time for an algorithm to execute.

Additional Information

 In addition, every algorithm must satisfy the following criteria:

• input: there are zero or more quantities that are externally supplied;
• output: at least one quantity is produced;
• definiteness: each instruction must be clear and unambiguous;
• finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps;
• effectiveness: every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation is definite, but it must also be feasible.