Algorithms Run time Complexity

Question

Hi I suppose to write a program that show the run time complixity I solved two but can't solve the third the code is :

{
class Program
{
    /* static long F1(long n)
     {
         long sum = 0;
         for (int k = 1; k <= n; k++)
         {
             for (int j = 1; j <=n*n; j++)
             {
                 for (int m = 1; m <=j; m++)
                 {
                     sum = sum + 1;
                 }
             }
         }
         return sum;
      }
    static long F2(long n)
     {
         long sum = 0;
         for (int k = 1; k <= n; k++)
         {
             for (int j = 1; j <= n ; j++)
             {
                 for (int m = 1; m <= j; m++)
                 {
                     sum = sum + 1;
                 }
             }
         }
         return sum;

     }*/
  static long F3(long n)
  {
      long prod = 1;
      long m;
      long i = 2;
      long s = n;
      while (n >= 1)
      {
          m = 1;
          while (m <= n)
          {
              prod = prod * 2;
              m = m + 1;
          }
          n = s / i;
          i++;
      }
         return prod;

     }


    static void Main(string[] args)
    {
       // Console.WriteLine(F1(100));
       // Console.WriteLine(F2(2200));
     Console.WriteLine(F3(10000));
        long x; 
        DateTime d1=DateTime.Now;
        x=d1.Ticks;
     // F1(600);  
    //    F2(2200);
        F3(1000);
        DateTime d2=DateTime.Now;
        x=(d2.Ticks-x)/10000000;
        Console.WriteLine("x=" + x.ToString());
        Console.ReadLine();
    }
}

}

now the correct answers that F3 should show are

300000000   0   5
400000000   0   4
500000000   0   7

but all what i got is o o o

while the F2 and F1 are showing right answers can any one help

Determine RunTime Complexity for each of the following functions and the code should show the results i posted — mohd qawas
– mohd qawas, Commented Jul 9, 2010 at 13:18
You forgot to say what problem you are trying to solve. You saved some time with less typing, but you are wasting time of all readers. — Dimitris Andreou
– Dimitris Andreou, Commented Jul 9, 2010 at 13:20
For your second question: System.out.println("300000000 0 5\n400000000 0 4\n500000000 0 7"); — Dimitris Andreou
– Dimitris Andreou, Commented Jul 9, 2010 at 13:21
Is it only me that finds the question a bit confusing? The main method contains two WriteLine() calls, but the expected output contains three lines. The WriteLine() calls print one value each, and one of the values is prepended with "x=", but each line in the expected output contains three values, and the "x=" is nowhere to be seen. I suggest you specify what that expected output is more precisely. At least I am having a hard time understanding what you mean. — Alderath
– Alderath, Commented Jul 9, 2010 at 13:50

Jack · Accepted Answer · 2010-07-09 13:20:03Z

1

What I wonder is: isn't it just a matter of integer division?

I mean here: x=(d2.Ticks-x)/10000000;

Note: I'm not practical with C#, it's just an hypothesis

answered Jul 9, 2010 at 13:20

Jack

134k33 gold badges252 silver badges349 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

mohd qawas Over a year ago

the problem with the othe functions F1 and F2 every thing is fine but with F3 Im getting wronge answers

Jack Over a year ago

Maybe because F1 and F2 last more than 10000000 ticks while all runs of F3 are shorter: this will cause the output of three 0s.

Jacob Over a year ago

@Jack: Could F3 be pow(2,n)?

Jack Over a year ago

A float value like 10000000.0, but as stated I'm not fond of C#.. mine was just a guess, since when integer division is used these errors are likely to occur..

Jack Over a year ago

I see that Mau is using this conversation to update his answer :)

|

Mau · Accepted Answer · 2010-07-09 13:27:45Z

0

 x=(d2.Ticks-x)/10000000

is where the problem lies. F3 runs for less than a second and you are doing integer divisions: remember that 900/1000 == 0.

A simple (rather unelegant) fix is to do a floating point division:

 x=(d2.Ticks-x)/10000000.0

You might want to use TimeSpans intead, which are made to measure elapsed time:

DateTime start = DateTime.Now;

// Do stuff

DateTime end = DateTime.Now;
TimeSpan elapsed = end - start;
double secondsElapsed = elapsed.TotalSeconds;

edited Jul 9, 2010 at 13:27

answered Jul 9, 2010 at 13:21

Mau

14.5k2 gold badges33 silver badges53 bronze badges

Collectives™ on Stack Overflow

Algorithms Run time Complexity

2 Answers 2

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related