What is the time complexity of this function / algorithm?void f(unsigned int n){ int i; for (i = 1; i < n; i = i * 2) { printf("[%d]\n", i); }}
Question
What is the time complexity of this function / algorithm?void f(unsigned int n){ int i; for (i = 1; i < n; i = i * 2) { printf("[%d]\n", i); }}
Solution
The time complexity of this function is O(log n). This is because the loop counter 'i' is doubled in each iteration. As a result, the number of iterations will be proportional to the logarithm (base 2) of 'n'. Therefore, the time complexity is logarithmic, or O(log n).
Similar Questions
What is the time complexity of this function / algorithm?void f(int n){ printf("n = %d\n", n);}
What is the time complexity of this function / algorithm?void f(int n){ int i; for (i = 0; i < n; i++) { printf("[%d]\n", i); }}O(n)O(1)O(log(n))O(nlog(n))O(2^n)O(n!)O(n^2)
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 :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 is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
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.