What is the time complexity of the following algorithm?
int func(int n) {
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
printf("Hello");
}
}
}
What is the time complexity of the following algorithm?
int func(int n) {
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
printf("Hello");
}
}
}
Show Hint
To determine the time complexity of an algorithm, consider the number of iterations of each loop. The time complexity for nested loops is the product of the iterations.
O(n)
O(n²)
O(n³)
O(log n)
The Correct Option is B
Solution and Explanation
Understanding the Algorithm
- The outer loop runs n times.
- The inner loop also runs n times for each iteration of the outer loop.
- The total number of executions of the `printf` statement is \( n \times n = n^2 \).
Thus, the time complexity of the algorithm is O(n²).
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
Top GATE CS Programming in C Questions
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- Bird: Nest :: Bee: ............ ?
Given the following cache parameters:
\[ \begin{array}{|c|c|} \hline \textbf{Tag} & 4 \, \text{bits} \\ \textbf{Index} & 12 \, \text{bits} \\ \textbf{Block Size} & 1 \, \text{byte} \\ \hline \end{array} \]Find the size of the main memory and the size of the cache memory.
Consider the following process information for Shortest Remaining Time First (SRTF) scheduling:
\[ \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time (AT)} & \textbf{Burst Time (BT)} \\ \hline P1 & 0 & 10 \\ P2 & 1 & 13 \\ P3 & 2 & 6 \\ P4 & 8 & 9 \\ \hline \end{array} \]Find the turnaround time for each process.
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?