Understand time complexity of algorithm to generate strings

Question

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

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:

The first for (that adds 32 ASCII to the string) has a complexity of O(n)
The second one, that concatenates the surname string has a complexity about of O(n/2)
The third, that concatenates the name string has a complexity of about O(n/2)
The fourth, that concatenates the empty space with a single char of telephone number by 5 character sequentially, has a complexity of O(n/4)

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?

If you consider the length n as being variable, you have a finite number of steps each linear in n, so the complexity is linear. If you don't (your code hardcodes lengths), then it is constant. — Ami Tavory
– Ami Tavory, Commented Feb 13, 2016 at 9:08

Fredrik Savje · Accepted Answer · 2016-02-13 22:08:27Z

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.

Collectives™ on Stack Overflow

Understand time complexity of algorithm to generate strings

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related