Complexity of the jump search algorithm

Question

I need some help to count the complexity of the jump search algorithm

sorry it says I need to write more infos to get my question shared so just ignore this please , I really need it.

void jump_search(Pointeur_L1 P, int lenght, char * word) {
Pointeur_L1 inf, max;
max = P;
lenght = longueur_L1(P);
int step = sqrt(lenght);
bool r = false;
int i, j = 0;
while (j < longueur_L1(P)) {
 for (i = 0; i < step; i++) {
   max = max -> suiv;
 }
 if (strcmp(max -> mot, word) == 0) {
   printf("ce mot existe :");
   printf("dans la ligne %d a la position %d \n", max -> line, max -> pos);
   r = true;
 }
 if (strcmp(max -> mot, word) > 0) {
   while (max != NULL) {
     if (strcmp(max -> mot, word) == 0) {
       printf("ce mot existe :");
       printf("dans la ligne %d a la position %d \n", max -> line, max -> pos);
       r = true;
       max = max -> preced;
     } else {
       max = max -> preced;

     }
   }
 } else {
   inf = max;
 }
 j++;
}
if (max == NULL) {
 printf("ce mot n existe pas\n");
}
}

What about counting the comlexety (or profile the runtime) for different sizes of input to get a first idea? — MrSmith42, Jun 07 '21 at 12:46
I said I need help to count the complexity I don't have code errors — MAHDI MAMOUNI, Jun 07 '21 at 12:50
Take a look at this post: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm — g_od, Jun 07 '21 at 12:55
*"I don't have code errors"*: the code has errors. Try with a list of four values: 2->4->6->8, and search for the value 9. — trincot, Jun 07 '21 at 14:53

score 0 · Answer 1 · answered Jun 07 '21 at 15:08

Jump search cannot be efficiently implemented in standard (doubly) linked lists. The idea of jump search is that the algorithm can make one jump (of √n steps) in O(1) time, but that is not possible in linked lists: a single jump has a O(√n) time complexity since all intermediate nodes must be visited. And in the worst case O(√n) jumps have to be made, thereby visiting all nodes, giving an overall time complexity of O(n).

Bugs and inefficiencies

Your code has several issues:

The variable j is not used correctly: if searching for a value that is greater than all data in the list, then surely the outer loop will iterate too many times. That outer loop plans to iterate as many times as there elements in the list, but it should only loop at most √n times. Just do this without j and make the outer loop condition also: max != NULL, just like the inner one.
Also the for loop should be protected against null pointer exceptions. Include the max != NULL in the for loop's condition:
```
for (i = 0; i < step && max != NULL; i++) {
     max = max -> suiv;
}
```

If the searched word is not in the list, then the inner loop:

while (max != NULL) {

}

...will walk back the list all the way to the start of the list. This is a waste of time; it should stop looking further back when the value in the node is less than the searched value:

while (max != NULL) {
    int result = strcmp(max -> mot, word);
    if (result == 0) {
        printf("ce mot existe :");
        printf("dans la ligne %d a la position %d \n", max -> line, max -> pos);
        return;
    }
    if (result < 0) {
        break;
    } 
    max = max -> preced;
}
printf("ce mot n existe pas\n");
return;

You have variables inf, r which serve no purpose.
The function would be more useful if it would return something. It could be a boolean, or the node that was found (and null when it was not found).
Don't print the result in this function. It is not good practice to mix I/O and logic in the same function. Printing is something that the main program should do, not a function like this. If you make the function return the found node (or null) then the caller can use that info for producting the output you need.

Jump Search comparisons

There is one thing where this jump search still does better than a trivial linear search in a linked list: it does not perform the comparison for each element in its forward search. The number of comparisons in jump search is O(√n). This is also true in this implementation, if the above corrections are made to it.

Complexity of the jump search algorithm

1 Answers1

Bugs and inefficiencies

Jump Search comparisons