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
2,017 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).
commented May 6, 2014 by Prakash
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?
commented May 6, 2014 by Salil Agrawal

Similar Questions
+1 vote
Find all pairs of from two arrays which adds up to a specific sum?

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
Give an example of Algo/Program whose time complexity is O(log log n) ?

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)

...