Algorithms and Data Structure : Part 2

Q1) Given  two 1-D array.


One array has  consecutive odd numbers.
One array has consecutive even numbers.


Now  you have to sum each array and find the difference between these arrays.


How much space and time will be needed ? 


The input will be given in text file.


Ex : In you text file you will have


8 10 12 14
11 13 15 17 19


So you have to do :


Sum of even = 44
Sum of odd : 75


diff : 31 ,  even negative diff print if allowed.








Read Once you have working code:


If you use mathematical formula of  sum of N numbers, then you can do this operation in O(1) time, constant time.


And space you have two define just  THREE/FOUR INTS in you code.


Two ints to take start and end value of array, and  Two ints to save the sum, ( we can reuse one of previous int here) .


Now but if you would have read the full arrays and stored them and then find sum using for loop


then


TIME : O(n)
Space : 2N + some ints.


I have to start working on Arduino , that will be better for checking Memory and Execution Time.




Complexities:


O(1) >> O(logn) >> O(n) >> O(nlogn)


After this  O(n2) and above are just bad.... Try to keep  time complexity  =< O(n2)


Time Taken


When I run some basic loops on my Virtual machine having one CPU, below is time I got


linear loop with 10^5  close to 2 sec.
10^4 * log(10^4)  close to 1.5 sec.


So you can see once you have rough idea about how your machine will behave for MAX size of input, you need to change your ALGO and DATA STRUCTURE.


If data size is less than 100,  lot of time the difference in DATA STRUCTURE and ALGO is not visible.