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.
Here you have a simple double loop:
for i=1;i<=n;i++
for j=1; j<=n/6; j++
so if you count how many times the body of the loop will be executed (i.e. how many times this line of code sum = sum + 1; will be executed), you will see it's:
n*n/6 = n²/6
which in terms of big-O notation is:
O(n²)
because we do not really care for the constant term, because as n grows, the constant term makes no (big) difference if it's there or not!
When and only when you fully realize what I am saying, you can go deeper with this nice question: Big O, how do you calculate/approximate it?
However, please notice that such questions are more appropriate for the Theoretical Computer Science, rather than SO.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments