What is the time complexity of this function / algorithm?void f(unsigned int n){ int i; int j; for (i = 0; i < n; i++) { for (j = 1; j < n; j = j * 2) { printf("[%d] [%d]\n", i, j); } }}O(n)O(1)O(log(n))O(nlog(n))O(2^n)O(n!)O(n^2)
Question
What is the time complexity of this function / algorithm?void f(unsigned int n){ int i; int j; for (i = 0; i < n; i++) { for (j = 1; j < n; j = j * 2) { printf("[%d] [%d]\n", i, j); } }}O(n)O(1)O(log(n))O(nlog(n))O(2^n)O(n!)O(n^2)
Solution
The time complexity of the given function is O(n log(n)). Here's why:
The outer loop runs n times, and the inner loop runs log(n) times. This is because j doubles with each iteration, so it takes log(n) iterations for j to reach n.
Since the loops are nested, we multiply the complexities of the two loops together to get the total time complexity. Therefore, the time complexity of the function is O(n log(n)).
Similar Questions
What is the time complexity of this function / algorithm?void f(int n){ printf("n = %d\n", n);}O(n!)O(2^n)O(1)O(n)O(nlog(n))O(n^2)O(log(n))
What is the time complexity of this function / algorithm?void f(int n){ int i; for (i = 0; i < n; i += 98) { printf("[%d]\n", i); }}
What is the time complexity of the following code? for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { System.out.println(i * j); } } a. O(n) b. O(2^n) c. O(n^2) d. O(n log n)
What is the time complexity of the following code :int i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n/2; }}
What will be the time complexity of the following code?int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2){ for (int j = 0; j < i; j++){ count += 1;| } }return count;
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.