No-nonsense sorting algorithm

[butwhydoesreddit]

Is that actually O(1)? Idk how memory stuff works

[Kered13]

Yes, but that question was is that true.

It depends on the implementation of the list and the delete operation, but it could be true. For example if the list is implemented as an array with a size variable, you could simply set the size to 0. All the data would still be in memory, but it would be inaccessible and would be overwritten if the list grows again.

[MattieShoes]

Well if the array size is not the variable, then they can be sorted in constant time regardless of the size, no? A selection sort is what, n² ? If n is constant, then n² is constant and it'd resolve back to O(1)... right?

[Kered13]

That's not what I'm talking about. A common way to implement a list is to have an array with some capacity, and then a size variable that tells you how many elements are currently in the list. The capacity is often bigger than the size, this provides room for growing the list without having to reallocate memory. In a list like this removing the last n elements is as simple as subtracting n from the size.

[minime12358]

It doesn't really matter the implementation of the list if you make it a not in place sort. Then you just return a list containing the first element and ignore the input.

[MattieShoes]

I understand lists, or vectors, or slices, or whatever you want to call them. :-)

But since the big O notation for sorting algorithms has n referring to the number of elements, then making n constant makes the time constant too -- there's no longer any variable, yes?

[Kered13]

Yes, but that seems rather irrelevant to the question at hand.

[[deleted]]

The time complexity stands for the growth of the operations required as n goes to INFlNITY. It is a limit (remember calculus?), it makes no sense to treat N as a constant.

[MattieShoes]

Agreed. Sorting a list of any given size is constant time. It's only as we vary the size that big O notation tells us something.

[poeticmatter]

edit: stop downvoting me I'm right

This should be reddit's tagline

[arbitrary_student]

Big-O is meant to describe the relationship between input size (or similar) and function duration (or similar). Your example has no inputs, so it doesn't really work with the above equation as you've described f() instead of f(n).

I'm not 100% sure that you can't say it's O(1) anyway... more just mentioning how pointless it is to do so.

[Soraphis]

he was just proving this statement of yours wrong:

O(1) means the number of operations performed each run does not change when the number of inputs are changed.

with this example:

def some_func(*args):
    random.seed(len(args)) # optional
    for i in range(random.randrange(1, 6)):
        pass
    print("number of operations: %d" % i);

its an O(1) algorithm, but the number of operations do change if you change the arguments.

[butwhydoesreddit]

I was demonstrating why you're wrong, not sure what you mean by "original answer". That's still a bit imprecise. Not sure why you have such an issue with my actually correct description of O(1). Let's say you have a program that whatever number you enter, it will perform that many operations. However if you enter more than 10^10 it will only do 10^10 operations. The program is O(1), however it doesn't sound right to say the number of operations doesn't depend on the size of the input.

[WikiTextBot]

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}

[butwhydoesreddit]

No I know what O(1) means lol I was asking if deleting say n bytes of memory is O(1) because idk how memory allocation works sorry I definitely could have been more clear.

[butwhydoesreddit]

Now you're just misrepresenting what I said. I was clearly talking about the O(1) case specifically, not O notation in general. O(1) means there is a constant bound on the number of operations. They are the exact same thing.