CODEWITHSUNDEEP
algorithmcomplexity-theory
user1696230
user1696230

Reputation:

Determining time complexity of an algorithm

Below is some pseudocode I wrote that, given an array A and an integer value k, returns true if there are two different integers in A that sum to k, and returns false otherwise. I am trying to determine the time complexity of this algorithm.

I'm guessing that the complexity of this algorithm in the worst case is O(n^2). This is because the first for loop runs n times, and the for loop within this loop also runs n times. The if statement makes one comparison and returns a value if true, which are both constant time operations. The final return statement is also a constant time operation.

Am I correct in my guess? I'm new to algorithms and complexity, so please correct me if I went wrong anywhere!

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
    for (j=i+1, j<n, j++)
        if (A[i]+A[j]=k)
            return true
return false

Upvotes: 0

Views: 2343

Answers (3)

user1678380
user1678380

Reputation:

Yes. In the worst case, your algorithm is O(n2).

Your algorithm is O(n2) because every instance of inputs needs time complexity O(n2).
Your algorithm is Ω(1) because there exist one instance of inputs only needs time complexity Ω(1).

Following appears in chapter 3, Growth of Function, of Introduction to Algorithms co-authored by Cormen, Leiserson, Rivest, and Stein.
When we say that the running time (no modifier) of an algorithm is Ω(g(n)), we mean that no mater what particular input of size n is chosen for each value of n, the running time on that input is at least a constant time g(n), for sufficiently large n.

Given an input in which the summation of first two elements is equal to k, this algorithm would take only one addition and one comparison before returning true. Therefore, this input costs constant time complexity and make the running time of this algorithm Ω(1).

No matter what the input is, this algorithm would take at most n(n-1)/2 additions and n(n-1)/2 comparisons before returning value. Therefore, the running time of this algorithm is O(n2)

In conclusion, we can say that the running time of this algorithm falls between Ω(1) and O(n2). We could also say that worst-case running of this algorithm is Θ(n2).

Upvotes: 1

phant0m
phant0m

Reputation: 16905

Azodious's reasoning is incorrect. The inner loop does not simply run n-1 times. Thus, you should not use (outer iterations)*(inner iterations) to compute the complexity.

The important thing to observe is, that the inner loop's runtime changes with each iteration of the outer loop.

It is correct, that the first time the loop runs, it will do n-1 iterations. But after that, the amount of iterations always decreases by one:

  • n - 1
  • n - 2
  • n - 3
  • …
  • 2
  • 1

We can use Gauss' trick (second formula) to sum this series to get n(n-1)/2 = (n² - n)/2. This is how many times the comparison runs in total in the worst case.

From this, we can see that the bound can not get any tighter than O(n²). As you can see, there is no need for guessing.

Note that you cannot provide a meaningful lower bound, because the algorithm may complete after any step. This implies the algorithm's best case is O(1).

Upvotes: 5

Azodious
Azodious

Reputation: 13872

You are right but let me explain a bit:

This is because the first for loop runs n times, and the for loop within this loop also runs n times.

Actually, the second loop will run for (n-i-1) times, but in terms of complexity it'll be taken as n only. (updated based on phant0m's comment)

So, in worst case scenerio, it'll run for n * (n-i-1) * 1 * 1 times. which is O(n^2).

in best case scenerio, it's run for 1 * 1 * 1 * 1 times, which is O(1) i.e. constant.

Upvotes: -2

Related Questions