Jan 29, 2015 at 7:02am UTC
Would the big oh notation of the Algorithm of:
for ( j = 0; j < n; j++ )
{
for ( k = j; k < n; k++ )
{
<some operation>
}
}
be : O(N^2) because there are 2 for loops increasing the count?
thanks for your help.
Jan 29, 2015 at 8:06am UTC
well, with my limited knowledge of big o i think i can answer this: it is O(n2 ) because the inner loop is O(n), and each iteration of the outer loop is O(n), so thats O(n * n) which is O(n2 )
Jan 29, 2015 at 9:13am UTC
It is actually O(n2 )·O(<some operation> ) .
It depends on cost of some operation too. In case where it is O(1), total cost will be O(n2 )
Jan 29, 2015 at 12:03pm UTC
It's a bit more complicated (due to k=j) : O(n2 - ((n2 - n) / 2)).
Tip: replace <some operation>
with (e.g.) ++sum
and you'll find out whether your formular is correct.
[EDIT]
Simplifyed: O((n2 + n) / 2)
Last edited on Jan 29, 2015 at 12:44pm UTC