Clever Geek Handbook

Big O remark with absolute cost?

I will cover some books with questions about programming assignment and I saw a link to "O(|A|)"

time complexity. I've never seen this notation with an absolute value specified.

Some research led me to Big O Cheatsheet , which refers to this notation in the graphs section. The problem I am looking into is splitting the array, which is not really a graph issue (although I risk showing my ignorance with this statement perhaps).

Whether it refers |A|

to the size of the array or another number of elements, i.e. O(N)

?

+3


source to share


2 answers


In set theory, |A|

there is a cardinality of a set A

, in other words, the number of elements contained in a set A

.



Help: http://www.mathsisfun.com/sets/symbols.html

+5


source


You will see this symbol whenever A

it is not a number.

A

there can be many, therefore it |A|

depends on the context. For example.



  • A

    is a lattice vector, therefore |A|

    is the length of the vector.
  • A

    is a (possibly unknown) algorithm (like an attacker for encryption) then it |A|

    could be the complexity of that algorithm or the length of the random bit vector that the algorithm uses.
  • A

    is a set, that is, the |A|

    number of elements in a set, as Kostub Desmuh mentioned.

There may be many more cases.

0


source






More articles:


All Articles