Determining time complexity of an algorithm

Question

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

There's a little more to it than your explanation - see [triangle numbers](http://en.wikipedia.org/wiki/Triangular_number). 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. — , Sep 25 '12 at 05:48

score 5 · Accepted Answer · edited May 23 '17 at 12:12

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

edited May 23 '17 at 12:12

Community

1
1

answered Sep 25 '12 at 08:36

phant0m

16,595
5
50
82

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 '12 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 '12 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 '12 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 '12 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 '12 at 10:35
Please edit your answer, so I can upvote it, other then the last sentence - I find it is very informative and helpful for people who are new to computer science. – amit Sep 25 '12 at 10:37
@amit I have edited it. What do you think? (I dislike thinking about what an "average case" is, which is why I'm uncomfortable giving average-case bounds, unless I can back that up with formulas) And yes, your comment #2 is correct. – phant0m Sep 25 '12 at 10:42
`"The thing is - it is also the correct bound for worst case analysis."` This applies to all algorithms. If an algorithm is `O(g)` (where g is the tightest bound), you can always say "the algorithm is `Omega(g)` in the worst case", which is not informative either, or just redundant. – phant0m Sep 25 '12 at 10:45
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/17115/discussion-between-amit-and-phant0m) – amit Sep 25 '12 at 10:46

score 1 · Answer 2 · 2012-09-25T18:29:24.490

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

Your algorithm is O(n²) because every instance of inputs needs time complexity O(n²).
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(n²)

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

Do not confuse *Best Case Analysis* with Omega notation. They are different things. — amit, Sep 25 '12 at 10:28

Azodious · Answer 3 · 2012-09-25T09:53:59.450

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

edited Sep 25 '12 at 09:53

answered Sep 25 '12 at 05:47

Azodious

13,752
1
36
71

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 '12 at 08:39
@phant0m: Ok, I agree. it should be `(n-i-1)` and edited the answer. – Azodious Sep 25 '12 at 09: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 '12 at 10:11

Determining time complexity of an algorithm

3 Answers3