CODEWITHSUNDEEP
cstringalgorithmperformancetime-complexity
user3289840
user3289840

Reputation: 251

Understand time complexity of algorithm to generate strings

I have an algorithm that takes as input 3 strings, with a strcat concat for each letter like this: graphical representation of target algorithm

I have to find the time complexity of this algorithm:

char *Generate_ID(char *name,char * surname,char * telephone)
{
    int i=0,j=0,k=0;
    char s[19];
    for(i=0;i<18;i++) s[i]=' ';
    for(i=0;i<12;i+=2,j++)
    {
        if(surname[j]=='\0') break;
        s[i]=(surname[j]>='A'&& surname[j]<='Z')? (surname[j]) : (surname[j]-32); /*making uppercase*/
    }
    for(i=1,j=0;i<12;i+=2,j++)
    {
        if(name[j]=='\0') break;
        s[i] = (name[j] >= 'A'&& name[j] <= 'Z') ? (name[j]) : (name[j] - 32);      /*making uppercase*/
    }

    for(i=0;i<16;i++)
    {
        if (s[i] == ' ')
            s[i] = telephone[(k++)+5];  
    }
    s[16] = (rand() % 26) + 'A'; /*generating random letter uppercase*/
    s[17] = (rand() % 26) + 'A'; /*generating random letter uppercase*/
    s[18]='\0';
    return s;
}

Then:

Now to calculate the sum of time complexity, do I have to do (n/4+n/2+n/2+n)?

Since we work with string that can differ max ten characters make sense to talk about Best Time and Worst Time? Is my reasoning right?

Upvotes: 3

Views: 605

Answers (1)

Fredrik Savje
Fredrik Savje

Reputation: 565

There are a couple of issues here.

  • Big-O notation is used to describe a function's growth rate. If f(x) is of order O(g(x)) it basically says that for large enough x's, f(x) < K * g(x) is true for some constant K. For this reason, we can disregard terms with lower order in sums and disregard constant factors in products. Practically, this boils down to that O(n), O(n/2), O(n/4) and O(n/4+n/2+n/2+n) are the same, namely O(n). (However, actual run time for a fixed sized input can be very different between algorithms with the same complexity -- this is both the strength and weakness of Big-O notation.)

  • Complexity is given as a function of the size of the input. In other words, we are asking what is the growth rate of the run time of the algorithm as it gets more and more input to process. In your case, the run time is independent of the input. All loops have a fixed stop condition (e.g., i < 18 in the first loop). No matter how large strings you give the function, it will only consider the first 18 characters. For that reason, the function's complexity is constant time or in Big-O notation O(1).

It's not really relevant to talk about worst-, average- or best-case complexity in your case (as they all the same). But, in general, one is primarily interested in the worst- or average-case complexity.

I suggest that you read up on complexity theory and Big-O notation to get a better sense of the topic.

Upvotes: 3

Related Questions