Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

RunTime Complexity

Posted on 2007-04-09
21
1,351 Views
Last Modified: 2008-02-01
Hi there Buddies.
I've already answered the first 2 Functions But I wanna know if my answers are true
But I couldnt find a solution for the 3rd function
Here is the Question
1. Let n=2k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2k) = k   ,,, so It’s O(k)
Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of 2k is 2k*log(2k)  = 2k * k  ,,, so It’s O(2k)
Prod =  2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21   = 2k  -  2


Thanks
0
Comment
Question by:nikorba
  • 7
  • 6
  • 4
  • +2
21 Comments
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
ID: 18880441
I gather that 2k means 2^k or 2**k

> Second Function :
> Complexity as a function of n  is n*log(n)
I don't think that's right
0
 
LVL 84

Expert Comment

by:ozo
ID: 18880446
> if ((j % Math.Sqrt(n))==0)
How many times would this be true?
0
 
LVL 84

Expert Comment

by:ozo
ID: 18880722
> Prod = 2k * 2k-1 * 2k-2 * 2k-3 * 2k-4 *2k-5 *………* 21  = 2k  -  2
Are you saying Prod is less than 2k?
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 12

Expert Comment

by:Sinoj Sebastian
ID: 18880988
Sorry, not an answer, just a point

log2(2k) = 1+log2(k)  {not k; log2(2^k)=k}
0
 
LVL 2

Author Comment

by:nikorba
ID: 18883037
Hi there ,,, well , there are some mistakes in the Question ,,, because I copied it from the word Document ,,, so I thought that the exponent will appear correctly ...I will fix it now
Here is the Question
1. Let n=2^k , Determine RunTime Complexity for each of the following 3 functions as a function of k.
2. Calculate  prod as function of k in each case.

static int F1(int n)
            {
                  int prod=1;
                  while (n>1)
                  {
                        prod = prod *n;
                        n=n/2;
                  }
                  return prod;
            }

static int F2(int n)
            {
                  int prod=1; int m;
                  while (n>1)
                  {
                        m=n;
                        while (m>1)
                        {
                              prod = prod *2;
                              m=m/2;
                        }
                        n=n/2;
                  }
                  return prod;
            }

static double F3(int n)
            {
                  double prod=1; int x=0;
                  for (int i=1; i<=n; i++)
                        for (int j=1; j<=n*n; j++)
                              if ((j % Math.Sqrt(n))==0)
                                    for (int m=1; m<=j; m++)
                                          prod=prod *2;
                  return prod;
            }



My answers for the first 2 Functions

First Function :
Complexity as a function of n is log2(n)
Complexity as a function of k is log2(2^k) = k   ,,, so It’s O(k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2
Second Function :
Complexity as a function of n  is n*log(n)
Complexity as a function of k is 2^k*log(2^k)  = (2^k )* k  ,,, so It’s O(2^k)
Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Thanks
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 65 total points
ID: 18883314
>> Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

Not really (as ozo already noted).

           2^(k(k + 1)/2)

is more like it ... can you explain why ?


>> Complexity as a function of n  is n*log(n)

That's not correct ... you have nested loops of the same type as in the first function ... what does that give complexity wise ?
0
 
LVL 2

Author Comment

by:nikorba
ID: 18949023
OZo didn't saw my 2nd comment :)
I think the 1st two functions are correct
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18949165
>> I think the 1st two functions are correct

No, see my previous post ...
0
 
LVL 2

Author Comment

by:nikorba
ID: 18949207
>>>No, see my previous post ...

I saw it,,,
try to solve it numerically
try a number with the F1
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 18949219
>> try to solve it numerically
>> try a number with the F1

What do you mean ?

You said :

      Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

And that's simply not true ... (see my earlier post)
0
 
LVL 84

Expert Comment

by:ozo
ID: 19170896
there were answers
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19170973
I agree ... nikorba apparently didn't believe us when we pointed out his mistakes ...
0
 
LVL 2

Author Comment

by:nikorba
ID: 19172044
I still think that my answers were right ,,, that;s it
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19172171
Then I wonder why you were asking our help, if you can't accept what we have to say ?
0
 
LVL 2

Author Comment

by:nikorba
ID: 19172206
I appreciate ur help ,,, at first I wasnt sure about my answers so I asked u
but after a while the I asked the lecturer and he said my answers were right
I really thank u so much for ur help but that what happened
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19172373
If your teacher says that this :

    Prod = 2^k * 2^(k-1) * 2^(k-2) * 2^(k-3 )* 2^(k-4) *2^(k-5 )*………* 2^1  = 2^(k)  -  2

is correct, then he's wrong :)

2^(k)  -  2 is smaller than 2^(k), while Prod is a lot larger. How can those two be equal ?

Try filling in k=3 for example. You say that :

    Prod = 2^3 * 2^(2) * 2^(1)  = 2^(3)  -  2
    Prod = 2^6  = 2^3  -  2
    Prod = 64  = 6

How can 64 be equal to 6 ???
0
 
LVL 20

Expert Comment

by:Venabili
ID: 19180227
OK - this is one of these "why the hell I recommended delete" :)

So what we do with the question?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 19186139
If nikorba still wants our help, then I'll be glad to provide that ... if not, then this question can be PAQ'd for ozo as he was first :)
0
 
LVL 2

Author Comment

by:nikorba
ID: 19276885
I'm sorry I discovered that I was wrong
sorry everyone :)
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

861 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question