u/Leading-Fail-7263

the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

Aren't there infinite possible inputs? How does that make sense?

Wikipedia says:

>In computer science, an abstract data type (ADT) is a mathematical model for data types, defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and represent the point of view of an implementer, not a user. For example, a stack has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a linked list or an array. Another example is a set which stores values, without any particular order, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in".

I really don't understand this at all. Can someone give an example of a Data Structure vs an Abstract Data Stucutre? Are they two implementations of the same thing?

I really don't understand what's going on here - surely every data stucture a programmer comes across is definitonally defined from "the POV of the user" otherwise ... he wouldn't be using it?