optimizing an array

[incognito]

I want to find the similar elements in two arrays.
I wrote a following program for that

#include<iostream>
using namespace std;


int main()
{
  int a[] ={5,3,2,1,4};
  int b[] = {1,5,3};


  for(int i=0;i<5;i++)
  {
    for (int j=0;j<3;j++)
    {
      if(a[i] == b[j])
      {
        int* p =&a[i];
       cout << "similar elements\n"<<*p<<endl;
        p++;
      }

    }
 }
return 0;
}

similar elements
5
similar elements
3
similar elements
1

Program works fine. So here are the questions.

1. What is complexity of this logic? // O(n^2) ?
2. How do I optimize it?

Please explain. Thanks in advance. :)

[Gaminic]

1:
It can't be O(n²), unless you specify that size(a) (|a|) must be equal to size(b) (|b|) [which is not the case], or there is some logical (linear) connection between |a| and |b| (e.g. |a| = n, |b| = |a|/c, for some constant c).

Considering the size of a and b could be anything as far as the code is concerned, it is defined by two inputs, not one. Thus, your complexity will be a function of these two inputs.

2:
It depends on the characteristics of the data. What will the sizes of a and b be? What will the range of a and b be? What will the context be? In the most generic case, looping over both arrays will be the only option you have. If you have more specific characteristics, you might be able to exploit those. For example, looking for equal elements in two sorted arrays is trivial and can be done in linear time (i.e. O(max(|a|, |b|)).

It also depends on the nature of the problem. Can a or b have identical elements in itself? (In other words: can '5' be in a twice, thrice, ...?) If so, do you care about the multiple hits, or is it a yes/no answer you want?

3:
Purely codewise: what's the point of line 19? You're incrementing a pointer that's being discarded on the next line due to its scope running out. I imagine line 17 is just for testing pointers rather than any funcitonal reason, but line 19 has no use at all.

[oonej]

for number 1) if i understand it correctly

you would create a function called O and send it a variable n

int O(int n); //function prototype, usually above main

int O(int n){ // function, usually below mains closing bracket
   n = n*n; // n^2
return n;
}

and to use it, do something like the following in main(){ ... }:
O(5);

returns 25, so to print this do something like

cout << O(5) << " " << O(2) << " " << O(12);

output is 25 4 124

hope this helps

[Gaminic]

@oonej: Point one refers to complexity theory. A common way to analyze the running time of an algorithm is by defining it in terms of input size. The O() stands for Big Oh notation*. O(n) means that the algorithm runtime grows linearly with the input size 'n', O(n²) means quadratic growth. For example, finding the maximum element in an array of size 'n' is O(n) (you need to check each item exactly once), while (naively) finding the maximum multiple of any two elements of an array of size 'n' is O(n²) (because you need to calculate every multiple i*j, and there are ~n² multiples).

*http://en.wikipedia.org/wiki/Big_O_notation

[incognito]

@Gaminic - Hey, thanks for your inputs. It helped a lot to understand things.

1. Still, If I have to calculate the complexity. How should I go about it?
2. Damn ! My interviewer asked me to optimize it. I said by sorting both the arrays. He then asked HOW? and then all I did was starting at him ;)
3. You are right. I just coded it lazily :D Didn't pay attention to it. Sorry. It is of no use.

[oonej]

@incognito

So the true response should of been a recursive algorithm to sort them by size, then check for each element until b is greater then A then check the following a similarly ?

[Gaminic]

1. Just think about it. For every element in a, you have to check every element in b. Call |a| n and call |b| m if you wish.
2. "Sort to optimize" is tricky, because sorting is a very expensive task (O(nlogn)). It might not be useful to sort the list if you're only going to check for multiples once. The annoying thing is that it's very difficult to "know" when it is and when it isn't, because Big Oh hides so much information.

Once you figure out the answer to 1 (it's easy, very easy), you can try answering 2. Knowing that sorting takes O(nlogn) and checking sorted lists for multiples takes O(n) [n >= m], you can take an educated guess to whether it's worth sorting the lists.

[edit]
To the "HOW?" question: there are many sorting algorithms. Some are general-purpose efficient, while others are great under specific conditions. For basic information, check the Sorting page on Wikipedia. For advanced information, google "Beating the n log n bound on sorting".

[incognito]

@oonej - Kind of, yes :)

@Gaminic - Sorry for late reply. True, Big Oh hides information. And I have a fair idea about algorithms but I was not sure what exactly he wants :) Anyway, thanks a lot for your help. Got to learn many things ;)