Thread replies: 17
Thread images: 2
Thread images: 2
File: 1101ffprau-1444846806-94.jpg (305KB, 2243x3000px) Image search:
[Google]
305KB, 2243x3000px
Anyone know how to find the 'precise' big O for this?
[code]
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
sum += i;
}
}
[/code]
It's one of these, but I'm too stupid to figure it out. My shit isn't adding up.
1. O(4N2 + 5N + 2)
2..O(2N2 + 7N + 2)
3. O(N(N + 1) / 2)
4. O(3N^2 + 11N + 4)/2
5. O(N2)
>>
>>8302534
I stopped caring about computer science when I was introduced to the concept of Big O notation. What a crock of shit. If your algorithm can only be analyzed by inventing an asymptotic limit that can't exist, like some kind of computer science deity , then you are fucking wrong and the computer science is flawed.
>>
File: 1460348954512.png (394KB, 445x441px) Image search:
[Google]
394KB, 445x441px
>>8302534
They're all correct.
>>
>>8302559
ya know, he ain't wrong
It's also O(1)
sum = (n-1)n(n+1)/6
>>
>>8302548
>/sci/ will actually fall for this copypasta
>>
>>8302534
It's 3
>>
>>8302534
It's 5. The time complexity is given by answer 3 but n(n+1)/2 is of order O(n^2).
You can work it out because the innermost operation is run n + (n-1) + (n-2) + ... + 2 + 1 times which is equal to n(n+1)/2
>>
>>8302534
>'precise' big O
It's Θ(n^2)
>>
>>8302534
I think it's 2, I'm going to submit my homework soon so I'll let you know whether I was right.
>>
>>
O (n^2)
If it was for (..){} and then a non-nested for loop it would be O (n + k)
>>
>comp sci majors proving once again that they are nothing more than code monkeys
>>
>>8302534
Why would you care about the exact big O and not just the type of complexity?
>>
"Precise"??? Big O
Big O notation doesn't have scaling factors or lower powers in it, that defeats the point, it's about dividing algorithms into broad complexity classes.
Because of how much backend variance there is due to the specific data set, execution architecture, and possible compiler optimization, there literally isn't anything more meaningful you can say about it besides O(n^2). The other ones give you no insight into judging actual run times.
>>
>>8302534
It's [math] \mathcal{O}(n^{2}) [/math]
>>
>>8302534
All of these are equal, but if you absolutely must count the operations, then it's 3.
Thread posts: 17
Thread images: 2
Thread images: 2