Big Oh help

[Josh]

Edit: I got it figure out now!

[Chris]

I'm extremely rusty, but this would be my results:

1) O(n^2)
2) O(n*log(n))
3) O(n*2^(n+1))
4) If anything, this halves the n run time not increases it, so O(1/2*n^2)
5) This should be the log run time, so... O(2*log(n)) or O(log(n^2))

Again, I am EXTREMELY rusty at O for algorithms, so I won't be the most help. I'd wait for someone who has used it recently.

Ironically though, if you want to know if n! ~ sqrt(2*pi*n)*(n/e)^n I can tell you it is.... But that's asymptotic, not run time.

[Josh]

Oct 28, 2010 19:04:11 GMT -8 Chris said:

I'm extremely, but this would be my results:

1) O(n^2)
2) O(n*log(n))
3) O(n*2^(n+1))
4) If anything, this halves the n run time not increases it, so O(1/2*n^2)
5) This should be the log run time, so... O(2*log(n)) or O(log(n^2))

Again, I am EXTREMELY rusty at O for algorithms, so I won't be the most help. I'd wait for someone who has used it recently.

Ironically though, if you want to know if n! ~ sqrt(2*pi*n)*(n/e)^n I can tell you it is.... But that's asymptotic, not run time.

Ok, thanks for your help. I really do appreciate it. Hopefully someone else can come along and explain it to me better. Thanks again.

[Chris]

Dunno how the word "rusty" disappeared from my above post... whoops.

The only one I'm 100% sure on is #1. The reason is because the for() in main runs for N-2 loops... it also calls test(N) each time, which runs for N-1. At infinity, we only care that this is N^2 beacuse that is much stronger than the -3n and +2 terms. (n-2)*(n-1) = n^2 - 3n + 2

[Josh]

Oct 29, 2010 6:33:41 GMT -8 Chris said:

Dunno how the word "rusty" disappeared from my above post... whoops.

The only one I'm 100% sure on is #1. The reason is because the for() in main runs for N-2 loops... it also calls test(N) each time, which runs for N-1. At infinity, we only care that this is N^2 beacuse that is much stronger than the -3n and +2 terms. (n-2)*(n-1) = n^2 - 3n + 2

Thanks for explaining the first one for me. Evidentally I have no idea what I am doing lol...hopefully someone else does and can explain to me better...thanks again