Runtime Analysis.... kind of.

[Sidoh]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

MyndFyre edit: changed the title

[iago]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

Nothing beats garbage sort. I don't know what the order is, but the algorithm is:

garbage_sort(list)
{
  while(!is_sorted(list))
  {
    shuffle(list)
  }
}

(My friend's algorithm, not mine :) )

[Sidoh]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

Nothing beats garbage sort. I don't know what the order is, but the algorithm is:

garbage_sort(list)
{
  while(!is_sorted(list))
  {
    shuffle(list)
  }
}

(My friend's algorithm, not mine :) )

Haha, yeah.  Well, the search space is O(n^n) (n^n is \Theta(n!)).  Since it's stochastic, there really isn't an order.  You could analyze the expected run time, but there is no "worst" case.  For any proposed finite worst case (i.e., n^n iterations), you could still do worse if you're unlucky.

[iago]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

Nothing beats garbage sort. I don't know what the order is, but the algorithm is:

garbage_sort(list)
{
  while(!is_sorted(list))
  {
    shuffle(list)
  }
}

(My friend's algorithm, not mine :) )

Haha, yeah.  Well, the search space is O(n^n) (n^n is \Theta(n!)).  Since it's stochastic, there really isn't an order.  You could analyze the expected run time, but there is no "worst" case.  For any proposed finite worst case (i.e., n^n iterations), you could still do worse if you're unlucky.

So it's O(∞). Good game, try finding a worse algorithm! :)

[Sidoh]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

Nothing beats garbage sort. I don't know what the order is, but the algorithm is:

garbage_sort(list)
{
  while(!is_sorted(list))
  {
    shuffle(list)
  }
}

(My friend's algorithm, not mine :) )

Haha, yeah.  Well, the search space is O(n^n) (n^n is \Theta(n!)).  Since it's stochastic, there really isn't an order.  You could analyze the expected run time, but there is no "worst" case.  For any proposed finite worst case (i.e., n^n iterations), you could still do worse if you're unlucky.

So it's O(∞). Good game, try finding a worse algorithm! :)

All algorithms are O(∞). :)

[iago]

Why in the world are you using a spin lock here?  I sure hope lock contention is low or the critical section is trivial.

I would guess it's for school.  (I had much worse assignments in my operating systems class).

Yeah, same. It's to learn how the stuff works, not how to use things properly. It's the same as the old "implement a bubble sort" thing.

Bubble sort is hardcore, but it's not quite as badass as stooge sort.  It has O(n^( log(3) / log(1.5) )), which is O(2.709...) running time! :D

Nothing beats garbage sort. I don't know what the order is, but the algorithm is:

garbage_sort(list)
{
  while(!is_sorted(list))
  {
    shuffle(list)
  }
}

(My friend's algorithm, not mine :) )

Haha, yeah.  Well, the search space is O(n^n) (n^n is \Theta(n!)).  Since it's stochastic, there really isn't an order.  You could analyze the expected run time, but there is no "worst" case.  For any proposed finite worst case (i.e., n^n iterations), you could still do worse if you're unlucky.

So it's O(∞). Good game, try finding a worse algorithm! :)

All algorithms are O(∞). :)

Well, it's O(∞) for any value n > 1. :)

[Sidoh]

All algorithms, regardless of input size, are O(∞).

The following is O(∞).
function :
  return 2;

Big-O denotes an upper bound.  It's often assumed that it's the "best" upper bound, and most text/literature uses it in this way, but it isn't something that's given to you automatically by using big-O.  If f(x) is O(g(x)), we know that f(x) is bounded above by g(x), but we don't know that it's bounded above.  If f(x) is Theta(g(x)), then it's bounded both above and below by g(x).  Big-O is used in place of big-Theta often because it's harder to prove a big-Omega (bounded below by) bound, and it isn't particularly useful for most things.

[iago]

Fine, then my algorithm has the worst case of ∞ for any input > 1. :P

(I haven't used big O or theta or omega since second year comp sci :P)

[Sidoh]

Fine, then my algorithm has the worst case of ∞ for any input > 1. :P

(I haven't used big O or theta or omega since second year comp sci :P)

That wording seems a little iffy.  Maybe it's acceptable, but I'd probably be a weeny and say it doesn't have a worst case.

heh, algorithms is one of things I've decided to study in more depth.  Asymptotic analysis is pretty important if you intend to do research that involves producing new stuff.

[iago]

Asymptotic analysis is pretty important if you intend to do research that involves producing new stuff.

Fortunately, I don't produce new stuff, I just break old stuff. :D

[iago]

Thanks for splitting it off.

Also, your new avatar looks too much like Ender's, I keep getting mixed up :)

[MyndFyre]

Thanks for splitting it off.

Also, your new avatar looks too much like Ender's, I keep getting mixed up :)

Uhhh.....


I can't say I see the similarity.   :o

[Blaze]

Thanks for splitting it off.

Also, your new avatar looks too much like Ender's, I keep getting mixed up :)

Uhhh.....


I can't say I see the similarity.   :o

Try:

[MyndFyre]

Thanks for splitting it off.

Also, your new avatar looks too much like Ender's, I keep getting mixed up :)

Uhhh.....


I can't say I see the similarity.   :o

Try:

I don't see that avatar.

[Sidoh]

See no evil? :O

Does this one look better, iago?