Exams › GATE › Technical

Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the function is

1. Θ(n²)
2. Θ(n² log n)
3. Θ(n³)
4. Θ(n³ log n)

Correct answer: Θ(n² log n)

Solution

The function has two nested loops: the outer loop runs for n/2 to n, which is Θ(n), and the inner loop runs logarithmically with respect to n (specifically, it doubles j each iteration). Therefore, the total complexity is the product of these two, resulting in Θ(n² log n).

Related GATE Technical questions

• The truth table X Y f(X,Y) 0 0 0 0 1 0 1 0 1 1 1 1 represents the Boolean function
• The decimal value 0.5 in IEEE single precision floating point representation has
• A process executes the code fork(); fork(); fork(); The total number of child processes created is
• The protocol data unit (PDU) for the application layer in the Internet stack is
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
• A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

⚔️ Practice GATE Technical free + battle 1v1 →