Time complexity of an algorithm where the input is known?

user_12114587 0
Viewed 2395

Learning about algorithms and I am slightly puzzled when it comes to calculating Time Complexity. To my understanding, if the output of an algorithm does not depend on the input size, it takes constant time i.e. O(1). Whereas when it does depend on the input, it is known as linear time i.e. O(n).

However, how does the time complexity work out when we know the size of the input?

For example, I have the following code which prints out all the prime numbers between 1 and 100. In this scenario, I know the size of the input (100) so how would that translate to the Time Complexity?

public void findPrime(){

    for(int i = 2; i <=100; i++){
        boolean isPrime = true;
        for(int j = 2; j < i; j++){
            int x = i % j;
            if(x == 0)
                isPrime = false;
        }
        if (isPrime)
            System.out.println(i);
    }
}

In this case, would the complexity still be O(1) because the time is constant? Or would it be O(n) n being the i condition which affects the number of iterations for both for loops?

Am I also right in saying that the condition of i affects the algorithm the most in terms of run time? Greater the i, the longer the algorithm runs for?

Would appreciate any help.

time-complexity algorithm java
4 Answers

The output is not dynamic and always the same (like the input), which is per definition a constant. The complexity of calculating that is constant, it's always the same. If the upper bound was not fixed, then the complexity wouldn't be constant.

To introduce a dynamic upper bound, we need to change the code and check out the complexities of the lines:

public void findPrime(int n){

    for(int i = 2; i <= n; i++){     // sum from 2 to n
        boolean isPrime = true;      // 1
        for(int j = 2; j < i; j++){  // sum from 2 to i - 1
            int x = i % j;           // 1
            if(x == 0)               // 1
                isPrime = false;     // 1
        }
        if (isPrime)                 // 1
            System.out.println(i);   // 1, see below
    }
}

As the number i gets longer and longer, the complexity to print it is not constant. For simplicity, we say that printing out to System.out is constant.

Now when we know the complexities of the lines, we translate that into an equation and simplify it.

enter image description here

As the result is a polynomial, due to the properties of O notation, we can see that this function is O(n^2).

As the other answers have shown, you can also say it's O(n^2) by "locking at it". You need mathematical proofs only for more difficult cases (and to be sure).

user_123232480

If algorithm scalability depends on the input size, it's not always/necessarily only O(n2). It may be Qubic O(n3), Logarithmic O(log2(n)) or etc.

When algorithm doesn't depend on the input size, i.e. you have a constant amount of static operations which don't grow when your input grows - that algorithm is said to have a Constant Time Complexity which in asymptotic notation is O(1).

Usually, we want to measure Worst Cast Complexity for the algorithm, because that is what interests us for increasingly/sufficiently large inputs (for small inputs, mostly, it doesn't make any difference). So, the worst case is the case, when every possible iteration will execute/happen.

Now, pay attention to your double-for-loop. If you'll have your static range [2, 100] in your code, of course, if will always hit 3 as the first prime number, and every execution will have a Constant Time Complexity **O(1)**m but usually, we want to find prime numbers in some dynamically given range, and if that's the case, then, in the worst case, both loops may iterate over entire array, and as array grows - number of iterations, hence operations, will grow.

So, your code's worst-case time complexity is definitely O(n2).

user_15535370

Whereas when it does depend on the input, it is known as linear time i.e. O(n).

That's not true. When it depends on the input size, it is simply not constant.

It could be polynomial, meaning that it's complexity is represented as a polynom f(n).

Here, f(n) could be anything that is a polynom with parameter n - examples for this are:

  • f(n) = n - linear
  • f(n) = log(n) - logarithmic
  • f(n) = n*n - squared
  • ...and so on

f(n) could also be an exponent, for example f(n) = 2^n, which represents an algorithm, which complexity grows very fast.

user_10031420

Time complexity denpend on what algorithm you use. You can calculate time complexity of an algorithm by using follow simple rules:

  • Primitive expression: 1
  • N primitive expressions: N
  • If you has 2 separate code blocks, 1st code block has time complexity is A, 2nd code block has time complexity is B, so total time complexity is A + B.
  • If you loop a code block N times, code block has time complexity is M, so total time complexity is N*M
  • If you use recursive function, you can calculate time complexity by using Master theorem: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

Big O notation is a mathematical notation (https://en.wikipedia.org/wiki/Big_O_notation) describes the bound of a function. Time complexity is usually a function of input size, so, we can use big O notation to describe bound of time complexity. Some simple rules:

  • constant = O(constant) = O(1)
  • n = O(n)
  • n^2 = O(n^2)
  • ...
  • g(a*f(n)) = O(f(n)) with a is a constant.
  • O(f(n) + g(n)) = O(max(f(n), g(n))
  • ...
user_98727330
Related