Solved

RunTime Complexity

Posted on 2007-04-09
21
1,352 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
On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

 
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: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

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

Suggested Solutions

Title # Comments Views Activity
Weighted least Squares Excel 32 1,126
How to alter this REGEX pattern to match whole words rather than parts? 5 81
Good Magazines technology related 4 119
Currency Conversion? 1 112
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
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…

756 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