The complexity of time and space algorithm - Big O Notation

Question

I am trying to analyze the Big- O- Notation of a simple algorithm, and since then I have been working with it. So I came up with an analysis and try to find out if this is correct according to the rules for the following code:

public int Add() { int total = 0; //Step 1 foreach(var item in list) //Step 2 { if(item.value == 1) //Step 3 { total += 1; //Step 4 } } return total; } 

• If you assign a variable or set, in this case, the complexity is determined in accordance with the rules of Big O O (1) . So the first phase will be O (1) . This means that regardless of the size of the input, the program will run for the same time and memory space.

• In the second step, the foreach is executed. The loop is pretty clear. According to the input, the cycle repeats or starts. For example, to enter 10, the cycle is repeated 10 times and 20, 20 times. Completely dependent on input. According to Big O rules, the complexity will be O (n) - n is the number of inputs. Thus, in the above code, the cycle repeats depending on the number of elements in the list.

• At this stage, we define a variable that defines the state check (see encoding step 3). In this case, the complexity is O (1) according to the Big O rule.

• In the same way, in step 4 there are also no changes (see encoding step 4). If the condition check is correct, then the variable total increases the value by 1. Thus, we write - the complexity is O (1) .

So, if the above calculations are perfect, then the final complexity is as follows:

 O(1) + O(n) + O(1) + O(1) or (O(1) + O(n) * O(1) + O(1)) 

I am not sure if this is correct. But, I think, I would expect some clarification on this issue, if this is not an ideal option. Thanks.

Answer 1

Your analysis is not entirely correct.

• Step 1 actually performs O (1) operations
• Step 2 actually performs O (n) operations
• Step 3 performs operations O (1), but is performed n times, therefore, its entire contribution to complexity is O (1 * n) = O (n)
• Step 4 performs operations O (1), but it is performed up to n times, therefore its entire contribution to complexity is also O (1 * n) = O (n)

The whole complexity is O (1) + O (n) + O (n) + O (n) = O (n).

Answer 2

Your calculations for steps 3 and 4 are incorrect, because both of these steps are inside the for loop.

so the complexity of steps 2,3 and 4 will be equal to O (n) * (O (1) + O (1)) = O (n) and when playing a club with step 1 it will be O (1) + O (n ) = O (n).

Answer 3

Designation Big O to describe the asymptotic behavior of functions. Basically, it tells you how fast the function grows or deviates.

For example, when analyzing an algorithm, you may find that the time (or the number of steps) that is required to complete a task of size n is determined

T (n) = 4 n ^ 2 - 2 n + 2

If we ignore the constants (which makes sense because they depend on the particular equipment on which the program is running) and the slower growing terms, we can say that "T (n)" grows in n ^ 2 order and writes: T ( n) = O (n ^ 2)

For a formal definition, suppose that f (x) and g (x) are two functions defined on a subset of real numbers. Will write

f (x) = O (g (x))

(or f (x) = O (g (x)) for x → infinity, to be precise) if and only if there exist constants N and C such that

| e (x) | <= C | g (x) | for all x> N

Intuitively, this means that f does not grow faster than g

If a is some real number, we write

f (x) = O (g (x)) as x-> a

if and only if there exist constants d> 0 and C such that

| e (x) | <= C | g (x) | for all x with | xa | <d

So, for your case it will be

O (n) for | f (x) | > C | g (x) |

Link from http://web.mit.edu/16.070/www/lecture/big_o.pdf

 int total = 0; for (int i = n; i < n - 1; i++) { // --> n loop for (int j = 0; j < n; j++) { // --> n loop total = total + 1; // -- 1 time } } } 

Big O Notation suggests that the value of a very large outer loop will run n times, and the inner loop will run n times

Suppose n → 100 than the total n ^ 2 10000 runtime