how do i get a lower time complexity with a nested loop

Question

Hi everyone i'm working on c and my code looks like this, basically it's an array and in every array[j] there is a number from 1 to 8, not in order and i'm trying to find where 1 is, and do some operations, then find 2 and do other operations etc.. till number 8:

for(i=1;i<9;i++)
   for(j=0;j<8;j++)
     if(array[j]==i)
       //and operations to do but they are not needed now;

I'm trying to find another way of doing this with less time spent in the cycle as the complexity can be (n^2). Someone advided me a hasing system to order things but i don't know if it's good enough. Thanks to everyone!

I'm not sure we have enough information to really answer this. What is the problem size? Do different instances of the problem have numbers other than 8, or is the number 8 fixed? — Patrick87
– Patrick87, Commented Aug 24, 2020 at 12:10
no the problem does not have a fixed size, basically i have an array of structs, the struct is like this typedef struct {int index; charstring}. And i have to print the strings in order as the struct.index is a casual number from 1 to n. With the nested loop it takes too much time to print everything. In case i have n=1000 the worst case will take O(nn) complexity and it's too much! — youztouz
– youztouz, Commented Aug 24, 2020 at 14:46
so, do you want a faster execution or do you want less O complexity? — user3629249
– user3629249, Commented Aug 24, 2020 at 23:44
stackoverflow is not here to design your code. Please post a minimal reproducible example and what you want to improve — user3629249
– user3629249, Commented Aug 24, 2020 at 23:46
less time complexity means faster execution in the worst cases, right? anyway what i needed was a less complexity way of doing the same thing and still wasn't able to find it — youztouz
– youztouz, Commented Aug 26, 2020 at 13:24

sebastian · Accepted Answer · 2020-08-23 15:37:17Z

3

Quicksort has an average complexity of O(n log(n)). Sort the pair (value, index) by index so you can access them in O(1).

struct pair
{
    int val;
    int index;
};

int pair_compare(const void* a, const void* b)
{
    struct pair* x = (struct pair*)a;
    struct pair* y = (struct pair*)b;

    return x->val > y->val;
}

int main()
{
    int arr[8] = {4,2,1,3,6,5,8,7};
    
    struct pair* pairs = (struct pair*) calloc(8, sizeof(*pairs));

    int i;

    for(i = 0; i < 8; ++i)
    {
        pairs[i].val = arr[i];
        pairs[i].index = i;
    }

    qsort(pairs, 8, sizeof(*pairs), pair_compare);

    for(i = 0; i < 8; ++i)
    {
        printf("val: %d\tindex: %d\n", pairs[i].val, pairs[i].index);
    }

    free(pairs);

    return 0;
}

edited Aug 23, 2020 at 15:37

answered Aug 23, 2020 at 15:26

sebastian

4121 gold badge4 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

e2r3p13 Over a year ago

qsort the array is slower than just iterate over it, so if there's no need to get the array sorted, it's better and less complex to just use a for loop as done in the og question

sebastian Over a year ago

Are you saying that the time complexity of two nested for loops is smaller than qsort's?

e2r3p13 Over a year ago

No, but if he sorts each array, he will use a qsort inside a for loop, I'm saying that iterating over each array is less complex than sorting each array

e2r3p13 Over a year ago

My bad, I misunderstood the question!

user3629249 · Accepted Answer · 2020-08-24 23:51:10Z

0

suggest the code have an outer loop going through the arrays of 8 structs

For each array of 8 structs, loop through that 8, placing the index into that array of structs into a separate array of 8 integers according to the value in the first field of each struct.

Then a loop that goes through that array of 8 offsets, one by one, performing the desired operation for that specified struct instance.

answered Aug 24, 2020 at 23:51

user3629249

16.6k1 gold badge18 silver badges17 bronze badges

Collectives™ on Stack Overflow

how do i get a lower time complexity with a nested loop

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related