Solved

RunTime Complexity

Posted on 2007-04-09
21
1,355 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
[X]
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
  • 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
Get MySQL database support online, now!

At Percona’s web store you can order your MySQL database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card.

 
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: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering 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

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
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…
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…

626 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