C longest line algorithm

user_15755023 0
Viewed 154

I want to Analyze the best and worst cases of the number of calls to the copy function. What will be the difficulty for the average case? please help me to understand this solution?

I think best case is 1 and worst n-1 am I right?

#include <stdio.h>
#define MAXLINE 1000 /* maximum input line size */
 
int get_line(char line[], int maxline);
void copy(char to[], char from[]); 
 
/* print longest input line */
int main() 
{
int es;
int len; /* current line length */
int max; /* maximum length seen so far */
char line[MAXLINE]; /* current input line */
char longest[MAXLINE]; /* longest line saved here */
es=0;
max = 0;
while ((len = get_line(line, MAXLINE)) > 0)
    if (len > max) 
    {
        es++;
        max = len;
        copy(longest, line);
    }
    printf("%d",es);
if (max> 0)  /* there was a line */
    printf("\nlongest is:%s\n", longest);
return 0;
}
 
/* get_line: read a line into s, return length */
int get_line(char s[], int lim)
{
int c, i;
 
 
for (i=0; i<lim-1 && (c=getchar()) !=EOF && c!='\n'; ++i)
    s[i] = c;
 
if (c == '\n')
{
    s[i] = c;
    ++i;
}
s[i] = '\0';
return i;
}
 
/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
int i = 0;
while ((to[i] = from[i]) != '\0')
    ++i;
}
time-complexity c algorithm
1 Answers

Best case

copy(longest, line) will be executed only once if the first get_line call returns the longest string out of all consecutive ones. For this case, time complexity is O(1) in respect to copy.

Worst case

If next line is longer than the previous one, then copy(longest, line) will be called as many times as the number of iterations in the while loop. Basically, in this case, time complexity is O(n), where n - number of iterations.

Average case

This one is trickier, and I know how to calculate the upper bound for it. So, I assume that lengths of your strings are uniformly distributed and are all different

So, for n iterations, there will be n different lengths and hence n! possible permutations. For a case, when the maximum is reached at the n-th iteration, there are (n-1)! combinations -> the probability that the maximum is reached at n is (n-1)!/n! = 1/n.

Now, the number of times that a maximum is reached till n-th step is 1 + 1/2 + ... + 1/n ~ log(n). As said before, it's an upper bound for the average complexity since lengths of your strings are not necessarily unique.

So, time complexity is O(log(n)) in respect to the copy method.

user_10553950
Related