-2
$\begingroup$

This question already has an answer here:

Code=>

What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore 2log n times it will execute 2) outer goes to n incrementing by 1 threfore n times

Hence for each value of outer loop innner executes n* 2log n times... Threfore O(n*2logn)

Que 1) Is this correct

Que2) If it is Correct then how to derive θ(theta), average case.

Please help me here

|cite|improve this question
$\endgroup$

marked as duplicate by David Richerby, Evil, quicksort, fade2black, Yuval Filmus Nov 23 '17 at 10:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael♦ Nov 23 '17 at 0:17
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael♦ Nov 23 '17 at 0:19
  • $\begingroup$ I will take care of that next time...i got it...its my mistake $\endgroup$ – JobLess Nov 23 '17 at 0:26
  • $\begingroup$ I will read it and then come back to this question...thanks for sharing these links $\endgroup$ – JobLess Nov 23 '17 at 1:11
  • $\begingroup$ Note that asking for "the big-O notation for some code" an expecting to be told an asymptotic runtime bound is like asking for "the decimal notation for some person" and expecting to be told their height. $\endgroup$ – David Richerby Nov 23 '17 at 9:19
0
$\begingroup$

There are a number of serious misunderstandings in this post.

  1. Assuming that this code takes a pair of starting values $x,n$ as an input, this code describes a function, $f(x,n)$. However, $f$ can be calculated exactly, and there's no reason to describe it in terms of big-O notation. Big-O notation is used to describe an upper bound on a value that you don't know the precise value of. If you're looking to describe the function this code expresses you should calculate it, not use big-O. This code gives the function $f(x,n)=x+6n$.

  2. Even if we ignore 1, I’m having trouble with your calculation. Where did the $\log(n)$ come from? The inner loop executes 6 times, rather than $2\log(n)$ times. I can elaborate on this point if you wish, but you can easily verify this by hand with small numbers.

  3. You cannot leave the $x$ out of an upper bound on the complexity of code if $x$ is a variable in the code that isn't constrained. You might describe this code as $O(x+n)$ but to describe it as $O(n)$ is wrong.

  4. $\Theta$ does not mean the average case complexity. $g=\Theta(f)$ when $g=O(f)$ and $f=O(g)$. Again, you shouldn't describe this using $\Theta$ because we can simply calculate the value exactly.

Despite point $2$, your answer (once we've amended it to be $O(x+n\log(n))$ isn't really wrong (assuming we are caring about an upper bound). This is because it's an upper bound that's bigger than the best description. In this sense, the code is also $O(x+e^{e^n})$. It's just that describing it as such is probably not helpful.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Actually i have a exercise problem in my Class Practice Book.. I am trying to find out running time of loops.. The second loop is getting decremented n/3 times with each Iteration hence i took log n there ....this link has answer why i took it as log n softwareengineering.stackexchange.com/questions/253421/… $\endgroup$ – JobLess Nov 23 '17 at 0:21
  • 1
    $\begingroup$ @GauravWawge The inner loop executes $6$ times. Why did you think that it executes $2\log(n)$ times? $\endgroup$ – Stella Biderman Nov 23 '17 at 0:22
  • $\begingroup$ I find the tone of this answer (especially the second bullet) rather obnoxious. Please tone it down. $\endgroup$ – David Richerby Nov 23 '17 at 9:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.