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.
Using Sigma notation, we can find the asymptotic bounds of your algorithm as follows:
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.
You make n*n/6 operations, thus, the time complexity is O(n^2/6) = O(n^2).
n * (n / 6) operations: the complexity is the same, but the result differs.