top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+5 votes
1,873 views
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)

...