none
time complexity RRS feed

  • Question

  • Problem-1 What is the running time of the following function?

    void Function(int n)

    {

    int i=1 ;

    int s=1 ;

    while( s <= n)

    {

    i++ ;

    s= s+i ;

    print(\*");

    }

    }

    Friday, September 29, 2017 5:40 AM

All replies

  • The loop will run for n times, so the complexity would be  

    void Function(int n)
    {
    int i=1 ;  // 1
    int s=1 ;  // 1
    while( s <= n)  //N
    {
    i++ ; // 1
    s= s+i ; // 1
    print(\*");  // 1
    }
    }

    (1+1)* N * (1+1+1) = 5N

    Neglecting the constant value 5 the complexity would be N as loop will run N times depending on the what is the value of variable n

    Hope it helps!



    [If a post helps to resolve your issue, please click the "Mark as Answer" of that post or click Answered "Vote as helpful" button of that post. By marking a post as Answered or Helpful, you help others find the answer faster. ]


    Blog | LinkedIn | Stack Overflow | Facebook
    profile for Ehsan Sajjad on Stack Exchange, a network of free, community-driven Q&A sites

    Friday, September 29, 2017 11:01 AM
  • Hi Sajjad irun,

    >>Problem-1 What is the running time of the following function?

    If you want to know the running time of the Function, you could use TimeSpan.

    Best Regards,

    Wendy


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Friday, October 6, 2017 3:00 AM
    Moderator
  • If you mean how many ‘*’ will be displayed, then check this formula:

       int number_of_iterations = (int)Math.Floor( Math.Sqrt( 1 + 8 * n ) - 1 ) / 2;

    Friday, October 6, 2017 6:17 AM
  • I think this is the answering the question as the asker is asking for something otherwise known as the big-O notation.

    However, there is something wrong that, the function only accept 1 input, so it does not fit the definition of linear time.

    I think the correct answer is undefined, as the you cannot deduce the time required by input size, which is always 1. 


    Monday, October 9, 2017 8:18 AM
    Answerer