What would be the worst time analysis of following code for Big Theta Notation: void func1(int [] A){ int incr = 1; while(incr < A.length){ for(int j = 0; j < A.length; j+=incr){ A[j] /= 2; } incr *= 2; } }
What would be the worst time analysis of following code for Big Theta Notation:
void func1(int [] A){
int incr = 1;
while(incr < A.length){
for(int j = 0; j < A.length; j+=incr){
A[j] /= 2;
}
incr *= 2;
}
}
I thought this would just be Theta(n^2) since it is nested loop, since I actually go through the progresses,
it does not seem same n square complexity like those nested loop whose index just raises by 1 each iteration.
outer while loop doubles its index everytime until it reaches condition and inner for loop get addition to its index by that doubled index from the outer loop
inner loop will half its number of iteration every time which will be something like n + n/2 + n/4 ... which will get close to 2n.
but I am not sure how I can relate this to outer loop.
consider that any other arithmetic operation to be constant c1, c2, c3, ...(for example, int incr = 1; is c1 and A[j] /= 2; is c2)
and consider operation that relates with iteration to n ex) n^2, n log n, etc...
how would I be able to express this complexity to equation such as ex) c1 * n^2 + c2 * n log n?
This does not have to be exactly same, but I just want some explanation with details for how can I describe this complexity in equation.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
