Solution:
func3 time complexity is explained below line by line.
int m= data.length; here the length of the array is fetched from data and it is assigned to m; which will take constant time which is O(1)
int t=m; O(1)
Now comes the loop which will decide what the time complexity of this function is going to be
So the loop is running until t becomes 1
let’s see how the t is decremented (what is the logic which is changing it), and based on that time complexity will be decided.
t= t/2; is the statement
suppose the value of t was 1024
so the value of t will change as
1024
512
256
128
64
32
16
8
4
2
If we observe the pattern here then we can say it is operating log t times.
there is an inner loop as well so whatever time the inner loop consume will be multiplied by log t, since the inner loop will be executed log t times
since the loop is controlled by the value of t, this loop will also run log t times.
So, over all time complexity for func3 is O(log^2 t) or we can say O(log^2 length), where length is the number of elements present in array data. Because t is assigned by m which is assigned by the value of the length of array data.
func4()
Since I have explained above how the time complexity will be calculated, here I will go through only the effective statements which drive the time complexity
so, here is only one loop and it is controlled by the value of variable bound which is assigned to the length of the array named data.
so the time complexity of func4 will be O(length), where length is the number of elements present in array data.
![void func3 (float] data) int m = data.length; int t = m; while (t>1) t=t/2; for (int j=0; j < m; j += t) { data[j]++ int func4(int[] A, int target) int bound = 1000, n A. length; if (n < bound) bound n; for (int i-0; i < bound; i++) f if (A[i] target) return i; return -1;](https://d2vlcm61l7u1fs.cloudfront.net/media%2F9b9%2F9b96b468-4914-4c68-be5a-2bb12b85cb37%2FphppkNJvn.png)
