Reducing the time complexity

[ikan]

I have a very simple program the time complexity of the function that I used in this program is O(mn)because it has a nested loop, I really need to reduce the time complexity to O(n)

Would you please help me with that

Thank you 
[code=c++]
#include <iostream.h>
#include<stdlib.h>
int *char_count( const char* DNA, const int *starts, const int *ends, char letter);
int main()
{
char string[40]="ACGAAAAGGGTGCGCCGGGGACTGGGGGTAT";
const int enda[6]={3,10,13,16,20,23};
const int starta[6]={1,2,9,12,15,18} ;
int *counta=new int [6];
cout<<"number of occurrance of nucelotid in each interval is: \n";

counta= char_count(string,starta,enda,'G') ;
for(int m=0 ;m<=5;m++)
cout<<counta[m]<<"\t";
delete [] counta;
getch();
return 0;
}
//******************
int *char_count( const char* DNA, const int *starts, const int *ends, char letter)
{
int *count=new int [6];
for(int l=0;l<=5;l++)
{
count[l]=0;
for (int i=starts[l];i<= ends[l]; i++)
if(DNA[i] == letter)
count[l] ++ ;
}
return count;


}

[abhishekm71]

Please use code tags, and proper indentation. Also, please tell us what your program does.

[lsk]

I don't know how to make it O(n).
But if for me I'll mem position of 'G' and loop start and end, the loop will be smaller.

i.e.
ACGAAAAGGGTGCGCCGGGGACTGGGGGTAT
I'll get G_array = [2,7,8,9,11,13,16,17,18,19,23,24,25,26,27] : position of G, will loop this once.

and loop check
end {3,10,13,16,20,23};
start {1,2,9,12,15,18} ;
:
(1) 1-3 = 1 ,
(2) 2-10 = 4,
(3) 9-13 = 3,
(4) 12-16 = 1,
(5) 15-18 = 3,
(6) 18-23 = 3

^
similar to O(n).

you can minimize more by using pointer point at where the loop start instead of starting at [0] for new set( such as end of (1) and start (2) ).

[Smac89]

Ok you want to reduce the time complexity to O(n), but O(n) in terms of what? The length of the DNA array (string[40])or the interval arrays ([6])?

What @terapaht has done above will improve the running time by a little, but if you take into account the time to prepare the array in that format, then it is still the same running time if not longer now.

Problems like this usually have little to no improvement from what you have done because no matter what you do, you will still have to check the larger array for where the letter occurs and you will still have to iterate a counter array to update the counter array to update the counts for each interval. implementation of @terapaht's answer:

int *reduce(const char* DNA, const int size, char letter) {
    int *DNASeq = new int[size];
    for (int t = 0; t < size; t++) {
        DNASeq[t] = (DNA[t] == letter);
        if (t > 0) DNASeq[t] += DNASeq[t - 1];
    }

    return DNASeq;
}

int *char_count( const char* DNA, const int *starts, const int *ends, char letter)
{
    unsigned size = strlen(DNA);
    int *fast = reduce(DNA, size, letter);

    size = strlen(starts);
    int *count = new int [size];
    for (int t = 0; t < size; t++)
    {
         // you can minimize more by using pointer point at where 
         // the loop start instead of starting at [0] for new set
         count[t] = fast[ends[t]] - fast[starts[t]];
    }
    delete [] fast;
    return count;
}

[ikan]

Thank you so much :)

[ikan]

Thank you all :))))))))))