for(int i = 1; i < n; i = i ∗ 2){
for(int j = 0; j < n; j++){
if(i == j){
for(int k = 0; k < n; k++){
// Do something elementary
}
}else{
// Do another elementary thing
}
}
}
I am doing some exercise, and can someone please help me to figure out the Θ of the above algorithm? I understand that if it was just the two outer nested loops, the time complexity should be Θ(nlogn). But I don't know how to treat the if-else statement. Many thanks in advance!
You execute the outer loop log(n) times, because you double the value for i every time
Then you execute the inner loop n times, and the last inner loop inf the if statement you execute once (if i == j holds) n times, this the whole inner loop needs n + n steps each time.
This gives you an upper bound of O(2n log(n)) and since constants do not change the asymptotic complexity the runtime is bounded by O(n log(n))
for(int i = 1; i < n; i = i ∗ 2){ ----------
for(int j = 0; j < n; j++){ ---------- |
if(i == j){ | |
for(int k = 0; k < n; k++){ ---- | |
// Do something elementary | (n | + n ) | * log(n)
} ---- | |
}else{ | |
// Do another elementary thing | |
} ---------- |
} |
} |
------------
Note that the most inner loop is executed only once per second most inner loop (!) and since the second most inner loop gets executed log n times (with having n steps) we have to add the n times for the most inner loop to the runtime of the second most inner loop and then multiply it with the overall time the seondmost inner loop is executed
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments