top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to find all sub arrays from an array in o(n) complexity?

+5 votes
How to find all sub arrays from an array in o(n) complexity?
posted May 5, 2014 by Atul Mishra

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button
I don't think it is possible since a given array has n* (n+1)/2 subarrays.So it's inherent complexity is O(n^2). Is it possible to find all permutations of a string in complexity less than O(n!)  :)... Also is it possible to find all combination of a group of items in complexity less than O(2^n).
I also have the similar understanding that finding all subarray of an array can not be achieved in o(n) time. Would you like to clarify further?

Similar Questions
+1 vote

Say you are given

int a[ ] = {1,2,3,4};
int b[ ] = {4,3,2,1};
int S = 5;

Now the task is to find all pairs of two number which adds up to S (One number from a and other number from b).

+1 vote

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

Contact Us
+91 9880187415
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Karnataka INDIA.