mIRC Home    About    Download    Register    News    Help

Print Thread
algorithmic time complexity #229571 09/02/11 02:05 PM
Joined: Oct 2005
Posts: 827
P
pouncer Offline OP
Hoopy frood
OP Offline
Hoopy frood
P
Joined: Oct 2005
Posts: 827
Hi guys,

Given a set of numbers and a number n, find if there are 2 numbers in the set that add up to n. (O(n lgn) time) is optimal, n^2 is the simple answer.

Firstly, how is n^2 the simple answer?

Say we have these set of numbers (total numbers = n = 4)

1 2 3 4 - find two numbers that will add up to 7

For the maximum number of possible comparisons.
1 + 2,
1 + 3,
1 + 4

2 + 1,
2 + 3,
2 + 4

3 + 1,
3 + 2,
3 + 4

4 + 1,
4 + 2,
4 + 3

That's 12 comparisons, so can anyone see where n^2 has come from? It seems like its actually O(n^2 - n)

Also, anyone see how could we optimize this so the time complexity is O(n logn)?

Last edited by pouncer; 09/02/11 02:07 PM.
Re: algorithmic time complexity [Re: pouncer] #229573 09/02/11 03:51 PM
Joined: Feb 2006
Posts: 546
J
jaytea Offline
Fjord artisan
Offline
Fjord artisan
J
Joined: Feb 2006
Posts: 546
ah, homework time again.

if i remember correctly, O(f(n)) is the same as O(f(n) + g(n)) if g is a lower order function than f. thus O(n^2 - n) is effectively O(n^2). look at the definition of big O notation again, i'm sure this result follows directly from it.

as for the optimal solution, i can think of one that has time complexity O(n) but also space complexity O(M) where M is the number you wish to sum to.

using your example, given a[4] = {1, 2, 3, 4}, initialize an array b[7] to all 0s. then loop from i = 0 to 3, set b[a[i]] = 1. then loop again, this time checking if (b[7 - a[i]] == 1). if true, then you've found 2 numbers that add up to 7 (namely a[i] and (7 - a[i])). of course, this solution only works if you're dealing with integers and those integers are bounded. and you'll have to go through some additional pains if you plan to handle negatives.

i can't really think of a reasonable solution that runs in O(n * log(n)). perhaps something involving an initial sort?


"The only excuse for making a useless script is that one admires it intensely" - Oscar Wilde
Re: algorithmic time complexity [Re: jaytea] #229579 09/02/11 07:09 PM
Joined: Apr 2004
Posts: 847
Sat Offline
Hoopy frood
Offline
Hoopy frood
Joined: Apr 2004
Posts: 847
Originally Posted By: jaytea
i can't really think of a reasonable solution that runs in O(n * log(n)). perhaps something involving an initial sort?

yes, eg sort the array, then for each x in the array use binary search to test for the presence of M-x


Saturn, QuakeNet staff
Re: algorithmic time complexity [Re: Sat] #229580 09/02/11 08:07 PM
Joined: Oct 2005
Posts: 827
P
pouncer Offline OP
Hoopy frood
OP Offline
Hoopy frood
P
Joined: Oct 2005
Posts: 827
Originally Posted By: Sat
Originally Posted By: jaytea
i can't really think of a reasonable solution that runs in O(n * log(n)). perhaps something involving an initial sort?

yes, eg sort the array, then for each x in the array use binary search to test for the presence of M-x


O(n * log(n))

Isn't O(n) (what jaytea posted) better than that though?

Re: algorithmic time complexity [Re: pouncer] #229581 09/02/11 08:30 PM
Joined: Apr 2004
Posts: 847
Sat Offline
Hoopy frood
Offline
Hoopy frood
Joined: Apr 2004
Posts: 847
Originally Posted By: pouncer
Isn't O(n) (what jaytea posted) better than that though?

It is indeed, as long as you can afford the space and your set of numbers consists of integers only (the O(nlogn) solution works with real numbers as well).


Saturn, QuakeNet staff
Re: algorithmic time complexity [Re: Sat] #229583 09/02/11 09:01 PM
Joined: Oct 2005
Posts: 827
P
pouncer Offline OP
Hoopy frood
OP Offline
Hoopy frood
P
Joined: Oct 2005
Posts: 827
Originally Posted By: Sat
Originally Posted By: pouncer
Isn't O(n) (what jaytea posted) better than that though?

It is indeed, as long as you can afford the space and your set of numbers consists of integers only (the O(nlogn) solution works with real numbers as well).


yup, good point! Thanks alot guys.