Problem with complexity issue

Question

1.00/5 (1 vote)

See more:

Hey guys, i wish for good and clear explanation for this program complexity(space&time)
thx.

C#

#include <stdio.h>

void main()
{
    char s[50]="Crrosssection";
    int i,k=0;
    char res[50];

    for(i=0;s[i]!=0;i++){
          if(s[i]!=s[i+1]) res[k]=s[i],k+=1; 
    }
}

Posted 6-Feb-13 5:55am

idobry

Updated 6-Feb-13 6:04am

v4

Add a Solution

Comments

CHill60 6-Feb-13 12:00pm

It's not clear what your question is

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Manfred Rudolf Bihy · Answer 1 · 2013-02-06T06:38:00

Solution 2

The space complexity O(2n) where n is the string buffer size.
The time complexity is O(m) where m is the actual size of the string.

BTW, what will happen if the string assigned to the buffer is more than 49 characters long?

Cheers!

Posted 6-Feb-13 6:38am

Manfred Rudolf Bihy

Comments

Sergey Alexandrovich Kryukov 6-Feb-13 18:39pm

My 5, and I can answer your last question:
In this case, the code will behave as having the time complexity of O(1) :-)
—SA

Manfred Rudolf Bihy 7-Feb-13 8:15am

Thanks Sergey!

And yes O(1) it should be, not that the program would do any significant work though! :)

Sergey Alexandrovich Kryukov 7-Feb-13 8:51am

Big O notation says nothing about usefulness of the results of calculation. :-)
Cheers,
—SA

Jibesh · Answer 2 · 2013-02-06T06:18:00

Solution 1

If you have Visual Studio Team System Installed it comes with Code Complexity Analysis tools. there are many free tools available for code complexity analysis try this one[^] or google [^] it for more tools.

Posted 6-Feb-13 6:18am

Jibesh