@Avenged: I think it is O(n^2), where n = strlen(str). This is because
strlen(str) itself is O(n), as it must search the string character by
character looking for the null character. Furthermore, I think that
the compiler probably cannot optimize strlen(str) out of the for loop,
so it is executed n times. Set int n = strlen(str) at the beginning of
the code and change the termination condition on the loops to i<n, and
it drops to O(n).
Dave
On Sep 28, 1:47 pm, Avenged <nitee...@gmail.com> wrote:
> Please tell me the *time* and *space* complexity of this program? I believe
> it should be : O(*n*) and O(*1*) respectively.
>
> #include<stdio.h>
> #include<string.h>
> #define SET_BIT(x,k) (x|=(1<<(k)))
> #define CHECK_BIT(x,k) (x&(1<<(k)))
> int main()
> {
> unsigned int i,ascii;
> int count1=0,count2=0;
> const char* str = "geekszforgeeks";
> for(i=0;i<strlen(str);i++)
> {
> ascii=str[i];
> if(CHECK_BIT(count1,ascii-'a'))
> SET_BIT(count2,ascii-'a');
> else
> SET_BIT(count1,ascii-'a');
> }
> for(i=0;i<strlen(str);i++)
> {
> ascii=str[i];
> if(!CHECK_BIT(count2,ascii-'a'))
> {
> printf("\nThe first non-repeated character is :
> %c\n",str[i]);
> break;
> }
> else
> continue;
> }
> return 0;
>
>
>
> }- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
