Menu
I'm trying to figure out the time complexity of this pseudocode given algorithm:
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n / 6; j++)
sum = sum + 1;
I know that the first line runs
n times
But I'm not sure about the second line.
381
f(n) = n(n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2... this is exactly the complexity of these nested loop.
The time Complexity of a loop is considered as O(Logn) if the loop variables are divided/multiplied by a constant amount. And also for recursive calls in the recursive function, the Time Complexity is considered as O(Logn).
HOWEVER, the conclusion is CONSISTENT: The nested loop is much FASTER. When the iteration time is 100^5, the difference is significant: 321.49 vs 210.05. There is about 1.53-time gap between them.
So we can say the complexity of each for loop is O(n) as each loop will run n times. So you specified these loops are not nested in a linear scenario for first loop O(n)+ second loop O(n)+ third loop O(n) which will give you 3O(n) .
Using Sigma notation, we can find the asymptotic bounds of your algorithm as follows:
110
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
