Time Complexity of a loop if the loop variables is reduced / increased exponenti

ID: 3863379 • Letter: T

Question

Time Complexity of a loop if the loop variables is reduced / increased exponentially by a constant amount as follows:

// Here c is a constant greater than 1

for (int i = 2; i <=n; i = pow(i, c)) {

// some O(1) expressions

}

//Here fun is sqrt or cuberoot or any other constant root

for (int i = n; i > 0; i = fun(i)) {

// some O(1) expressions

}

What is the returned value of the following function?

int Fun(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;

}

Time Complexity of a loop if the loop variables is reduced / increased exponentially by a constant amount as follows:

// Here c is a constant greater than 1

for (int i = 2; i <=n; i = pow(i, c)) {

// some O(1) expressions

}

So , This loop will run when cp = n , So Let us find our
take Log both the sides , we get
=> p log c = log n

=> p = O( logc n )
So the time complexity is O( logc n )

//Here fun is sqrt or cuberoot or any other constant root

for (int i = n; i > 0; i = fun(i)) {

// some O(1) expressions

}

So here, I is reducing by Some root to get it to 1
n/(sqrt n)p = 1
= > n = (sqrt n)p
= p = logsqrt n n => O(logsqrt n n )

What is the returned value of the following function?

int Fun(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;
Values returned for n starting from n = 0 to 9
0 2 3 12 16 24 30 60 72

return k;

}

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.