- #1
theRukus
- 49
- 0
Homework Statement
Determine the complexity of the following code:
Code:
for (i = 0; i < 2*n; i += 2)
{
for (j=n; j > i; j--)
{
a++;
}
}
The Attempt at a Solution
Well.. The first for block is O( n ) because i is incremented by 2 each loop up to 2n. The second block is O( logn ) as the number of runs gets smaller as j increases.
So.. the whole algorithm is O( n log n ).
Any help is appreciated, I'm pretty bad with Big-Oh notation