1
$\begingroup$

When we discuss data structures, linear typically means that we can iterate through the data sequentially. For example, a linked list or array can fall into this category while a binary search tree is a non-linear data structure.

On the other hand, when we discuss mathematical functions, a linear function $f(x)$ satisfies two properties.

  1. $f(u + v) = f(u) + f(v)$
  2. $f(cu) = cf(u)$

Can someone explain to me how these two ideas relate or does the word "linear" map to two different definitions?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

The word linear has several, related, meanings in the English language, for example:

  • Made, or designed to be used, in a step-by-step, sequential manner: this is the meaning most related to the data structure one. It is also used when talking about linear narratives, for example.
  • Of, or relating to, a class of polynomial of the form $y = ax+b$: this is where your linear algebra example comes from.
  • Of, or relating to, lines: this is where the names for the Linear A and Linear B scripts come from.

(List taken from wiktionary.)

The various meanings are obviously related on some level — perhaps by a line of metaphors – but they are not related in any formal sense, any more than simple groups are related to simple roots. Mathematical terms are arbitrary, and their names should not be construed as dictating their meanings.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't see how the "class of polynomial" example and the "of, or relating to, lines" example differ. Aren't those exactly the same thing? $\endgroup$
    – Neel Sandell
    Commented Nov 29, 2021 at 16:43
  • $\begingroup$ It really makes little difference; this is not English Language & Usage. $\endgroup$
    – Yuval Filmus
    Commented Nov 29, 2021 at 16:46
  • $\begingroup$ By the way, these definitions are taken from Wiktionary, so that’s where your doubt should be targeted. $\endgroup$
    – Yuval Filmus
    Commented Nov 29, 2021 at 16:53
1
$\begingroup$

Linear for data structures typically refers to an O(n) algorithm. I.e. the time is bounded by c.n for some constant c > 0. The function f(n) = c.n when represented in the Cartesian plane forms a straight line.

If you purely view linear as "iterating through the data sequentially" then this presumably refers to the fact that the data can be represented on a straight line, reflecting that one element can be accessed from another via a ``successor" function that fits the straight line order.

The term linear function f(x) satisfying 1) and 2) in your question can determine a straight line in 2 dimensions. A linear function is used in linear algebra and can represent more general ``linear structures", for instance a plane.

All of these are likely to be related to this last interpretation of linear parts of vector spaces.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.