0

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
1
  • There's a little more to it than your explanation - see triangle numbers. Intuitively, a triangle is half a square, but this triangle-with-steps is actually half a rectangle. Asymptotically, though, it still simplifies to O(n^2). No matter how big n gets, n * (n+1) is always less than 2n^2, so the difference is (less than) a constant factor.
    – user180247
    Sep 25, 2012 at 5:48

3 Answers 3

5

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).

9
  • Please do not confuse "Best Case analysis" with Omega notation ("lower bound"). The lower bound of the average and worst case of the algorithm is Omega(n^2). The best case of the algorithm is Theta(1) The last sentence in your answer is misleading. (though not mathematically wrong in this specific case, but will probably lead to mistakes if someone tries to follow this reasoning)
    – amit
    Sep 25, 2012 at 10:26
  • P.S. if I am not wrong, Omega(1) = {all positive or monotonically increasing functions}, so Omega(1) is not very informative :|
    – amit
    Sep 25, 2012 at 10:27
  • @amit You are right, it's not very informative. But it is the correct lower bound in general, not of the average case. Let me think about this for a minute.
    – phant0m
    Sep 25, 2012 at 10:31
  • The thing is - it is also the correct bound for worst case analysis. I suspect what you wanted to write is "The algorithm's best case is Theta(1), because ....". This is a common confusion between lower/upper bound and best/worst case analysis. Remember that the analysis is providing a function from the algorithm, while the big O/big Omega/big Theta are sets of functions for this analysis
    – amit
    Sep 25, 2012 at 10:33
  • I just saw the edit to your first comment. I think that's the best way to put it.
    – phant0m
    Sep 25, 2012 at 10:35
1

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).

2
  • Why not explain how you arrive at O(n²)?
    – phant0m
    Sep 25, 2012 at 8:45
  • Do not confuse Best Case Analysis with Omega notation. They are different things.
    – amit
    Sep 25, 2012 at 10:28
-2

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.

3
  • No, @user41419 was wrong and so are you. Because the amount of iterations is not constant for the inner loop, you should analyze it differently to make sure you get accurate bounds.
    – phant0m
    Sep 25, 2012 at 8:39
  • @phant0m: Ok, I agree. it should be (n-i-1) and edited the answer.
    – Azodious
    Sep 25, 2012 at 9:52
  • 1
    Yes, it runs n - i - 1 times, however, you can't multiply that with n (the line after bold). You need to sum over i, because i is not a constant. Btw, lower bounds are denoted with Ω(), not O()
    – phant0m
    Sep 25, 2012 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.