3

Why does the following code for each statement refer to big O constant (here I use 1 for the convention)?

I mean if the array size gets bigger the time complexity may get larger right? Also the number in total will get larger and larger, won't it affect the complexity?

Pseudocode:

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)
dreamcrash
  • 47,137
  • 25
  • 94
  • 117
Yan Skywalker
  • 119
  • 1
  • 10

4 Answers4

2

TL;DR: Because the Big O notation is used to quantify an algorithm, with regards of how it behaves with an increment of its input.

I mean if the array size gets bigger the time complexity may get larger right? Also the number in total will get larger and larger, won't it affect the complexity?

You are mistaken the time taken by the algorithm with the time-complexity.

Let us start by clarifying what is Big O notation in the current context. From (source) one can read:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Informally, in computer-science time-complexity and space-complexity theories, one can think of the Big O notation as a categorization of algorithms with a certain worst-case scenario concerning time and space, respectively. For instance, O(n):

An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).

So for this code:

def find_sum(given_array)
    total = 0
    for each i in given array:
      total+=i 
    return total

the complexity is O(n) because with an increment of the input the complexity grows linear and not constant. More accurately Θ(n).

IMO it is not very accurate to find out the complexity like:

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)

Since the Big O notation represents a set of functions with a certain asymptotic upper-bound; as one can read from source:

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

More accurate would be :

def find_sum(given_array)
    total = 0 # takes c1 time 
    for each i in given array: 
      total+=i # takes c2 time 
    return total # takes c3 time

So the time complexity would be c1 + n * c2 + c3, which can be simplified to n. And since both the lower and upper bounds of this function are the same we can use Θ(n) instead of O(n).

dreamcrash
  • 47,137
  • 25
  • 94
  • 117
0

Why does the following code for each statement refer to big O constant (here I use 1 for the convention)?

Not sure, ask the person who wrote it. It seems clear the overall runtime is not O(1), so if that's the conclusion they arrive at, they are wrong. If they didn't mean to say that, what they wrote is either wrong or confusing.

I mean if the array size gets bigger the time complexity may get larger right?

Yes, it might. Indeed, here, it will, since you are at least iterating over the elements in the array. More elements in the array, more iterations of the loop. Straightforward.

Also the number in total will get larger and larger, won't it affect the complexity?

This is an interesting insight and the answer depends on how you conceive of numbers being represented. If you have fixed-length numeric representations (32-bit unsigned ints, double-precision floats, etc.) then addition is a constant-time operation. If you have variable-length representations (like a big integer library, or doing the algorithm by hand) then the complexity of adding would depend on the addition method used but would necessarily increase with number size (for regular add-with-carry, an upper logarithmic bound would be possible). Indeed, with variable-length representations, your complexity should at least include some parameter related to the size (perhaps max or average) of numbers in the array; otherwise, the runtime might be dominated by adding the numbers rather than looping (e.g., an array of two 1000^1000 bit integers would spend almost all time adding rather than looping).

Patrick87
  • 27,682
  • 3
  • 38
  • 73
0

No answer so far address the second question:

Also the number in total will get larger and larger, won't it affect the complexity?

which is very important and usually not accounted for.

The answer is, it depends on your computational model. If the underlying machine may add insanely arbitrarily large numbers in constant time, then no, it does not affect the time complexity.

A realistic machine, however, operates on values of fixed width. Modern computers happily add 64 bit quantities. Some may only add 16 bit-wide values at a time. A Turing machine - which is a base of the whole complexity theory - works with 1 bit at a time. In any case, once our numbers outgrow the register width, we must account for the fact that addition takes time proportional to the number of bits in the addends, which in this case is log(i) (or log(total), but since total grows as i*(i-1)/2, its bit width is approximately log(i*i) = 2 log(i)).

With this in mind, annotating

  total+=i # O(log i)

is more prudent. Now the complexity of the loop

for each i in given array:
  total+=i # O(log(i))

is sum[1..n] log(i) = log(n!) ~ n log(n). The last equality comes from the Stirling approximation of a factorial.

user58697
  • 7,808
  • 1
  • 14
  • 28
-2

There is no way, that the loop:

for each i in given array: 
    total+=i

will run in O(1) time. Even if the size of input n is 1, asymptotic analysis will still indicate, that it runs in O(n), and not in O(1).

Asymptotic Analysis measures the time/space complexity in relation to the input size, and it does not necessarily show the exact number of operations performed.

Point, that O(1) is constant, does not mean that it's just one (1) operation, but rather it means, that this particular block (which takes O(1)) does not change when the input changes, and therefore, it has no correlation to the input, so it has a constant complexity.

O(n), on the other hand, indicates, that the complexity depends on n, and it changes depending on how the input n changes. O(n) is a linear relation, when input size and runtime have 1 to 1 correlation.

Correctly written comments would look like this:

def find_sum(given_array)
    total = 0 #this is O(1), it doesn't depend on input
    for each i in given array: #this is O(n), as loop will get longer as the input size gets longer 
      total+=i #again, O(1)
    return total #again, O(1)
Giorgi Tsiklauri
  • 9,715
  • 8
  • 45
  • 66
  • 4
    This answer contains a number of common mistakes when describing big O. O(1) does not mean that the time doesn't change when the input changes. It means that the operation takes a bounded amount of time. O(n) is not a linear relation, it's a function that's eventually bounded by a line through the origin. Also, it's not true that every O(n) function depends on n. For example f(n)=1 is O(n). – Paul Hankin Mar 13 '21 at 12:00
  • 4
    The definition of f=O(g) is that there's n0 and c such that n>=n0 implies |f(n)| <= |cg(n)|. So for example f(n) = n mod 1000000 is O(1), but isn't constant, and does depend on n. In words, O(1) means "bounded by a constant" and not "asymptotically constant". Often in the real world we use informal notions of complexity, but I think in answers it's more helpful to get the details right to avoid confusing people who are trying to understand the subject more rigorously. – Paul Hankin Mar 13 '21 at 14:44