Asymptotic Worst Case Time and Time Complexity MCQ Quiz - Objective Question with Answer for Asymptotic Worst Case Time and 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)

Solution :

Bellman‐Ford algorithm ( Finds shortest paths from a single source node to all of the other nodes in a weighted digraph ) : O(mn) ,where, n  is no of edges , m is no of nodes.

Kruskal’s algorithm (Using Greedy approach it find the minimum cost spanning tree ) - O(m*log n)

Floyd‐Warshall algorithm (Find shortest paths in a directed weighted graph with positive or negative edge weights ) - O(n³)

Topological sorting (Find linear  ordering of vertices for Directed Acyclic Graph (DAG) ) - O(n + m)

Therefore ,option 2 is correct.

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ⁿ

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.  

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

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