Recent questions tagged asymptotic-notations

0 votes

3 answers

1

By own
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$

asked Sep 22, 2019 in Algorithms by shubhamkks1005 (5 points) | 73 views

0 votes

2 answers

2

From asymptotic notation
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..

asked Sep 22, 2019 in Algorithms by shubhamkks1005 (5 points) | 46 views

0 votes

1 answer

3

Cormen Edition 3 Exercise 8.1 Question 2 (Page No. 194)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.

asked Jun 28, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 22 views

0 votes

1 answer

4

Cormen Edition 3 Exercise 3.2 Question 3 (Page No. 60)
Prove that $n!=\omega(2^n)$ and $n!=o(n^n)$.

asked Jun 26, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 21 views

0 votes

1 answer

5

Cormen Edition 3 Exercise 2.2 Question 4 (Page No. 29)
How can we modify almost any algorithm to have a good best-case running time?

asked Jun 25, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 30 views

0 votes

1 answer

6

Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?

asked Jun 12, 2019 in Algorithms by lolster (237 points) | 114 views

+3 votes

1 answer

7

asymptotic_Notations Self_Doubt
Please give an example case for which all the three conditions $f(n)\neq O(g(n))$, $f(n)\neq \Theta (g(n))$ and $f(n)\neq \Omega (g(n))$ holds true.

asked Jun 1, 2019 in Algorithms by Satbir Boss (23.9k points) | 210 views

0 votes

0 answers

8

#CLRS #Algorithm Doubt about randomized QuickSort.

asked May 27, 2019 in Algorithms by iarnav Loyal (8.4k points) | 520 views

0 votes

1 answer

9

Asymptotic Notation theta property
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?

asked May 26, 2019 in Algorithms by shubhojit1412 (5 points) | 163 views

0 votes

0 answers

10

What would be the upper and lower bound for this decreasing function or invalid case? #Algorithm #Asymtotic-notations

asked May 10, 2019 in Algorithms by aniketpatil32 (29 points) | 41 views

+1 vote

0 answers

11

Find Asymptotic upper bound (http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf)

asked Apr 19, 2019 in Algorithms by Mk Utkarsh Boss (36.5k points) | 121 views

0 votes

0 answers

12

Cormen Edition 3 Exercise 3.2 Question 8 (Page No. 60)
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 21 views

0 votes

0 answers

13

Cormen Edition 3 Exercise 3.2 Question 7 (Page No. 60)
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 8 views

0 votes

0 answers

14

Cormen Edition 3 Exercise 3.2 Question 6 (Page No. 60)
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 11 views

0 votes

1 answer

15

Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 40 views

+1 vote

0 answers

16

Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 13 views

0 votes

0 answers

17

Cormen Edition 3 Exercise 3.2 Question 1 (Page No. 60)
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 11 views

0 votes

0 answers

18

Cormen Edition 3 Exercise 3.1 Question 8 (Page No. 53)
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ ... all $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 20 views

0 votes

1 answer

19

Cormen Edition 3 Exercise 3.1 Question 7 (Page No. 53)
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 71 views

0 votes

0 answers

20

Cormen Edition 3 Exercise 3.1 Question 6 (Page No. 53)
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 20 views

0 votes

1 answer

21

Cormen Edition 3 Exercise 3.1 Question 4 (Page No. 53)
Is $2^{n+1} = O(2^n) $? $2^{2n} = O(2^n)$?$

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 54 views

0 votes

0 answers

22

Cormen Edition 3 Exercise 3.1 Question 3 (Page No. 53)
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 23 views

0 votes

1 answer

23

Cormen Edition 3 Exercise 3.1 Question 2 (Page No. 52)
Show that for any real constants $a$ and $b$, where $b > 0,$ $(n+a)^b=\Theta(n^b)$

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 37 views

0 votes

0 answers

24

Cormen Edition 3 Exercise 3.1 Question 1 (Page No. 52)
Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\Theta$ notation, prove that $max(f(n),g(n)) = \Theta(f(n)+g(n))$.

asked Apr 4, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 26 views

0 votes

0 answers

25

#Self-Doubt #Asymptotic-Notation
Is it true? $an^{2} = O(n^{2})$ for a>0 Also, what is the difference between Small-oh and Big-oh? Also, why we consider theta, omega as Big-oh sometimes, in the above problem, the answer is Big-theta but it is equal to big-oh. Why is it so?

asked Mar 21, 2019 in Algorithms by nishant_magarde (319 points) | 32 views

0 votes

2 answers

26

Self doubt
O(n-1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?

asked Mar 19, 2019 in Algorithms by Tanuj Guha Thakurta (175 points) | 84 views

+1 vote

1 answer

27

Asymptotic Notations
Q1) f(n) = n^(1-sin n) g(n) = n^(1+cos n) Relation between them ? Q2) f(n) = n^(1-sin n) g(n) = n^(2+cos n ) Relation between them ?

asked Mar 7, 2019 in Algorithms by Ashish Roy 1 (167 points) | 69 views

0 votes

1 answer

28

Time Complexity
I am unable to Find its time complexity using Iterative method… Will any one help me out with this . Thank you :)

asked Jan 18, 2019 in Algorithms by Nandkishor3939 Active (1.3k points) | 125 views

0 votes

0 answers

29

Algorithm analysis
Find a growth rate that cubes the run time when we double the input size. That is, if T(n) = X, then T(2n) = x^3.

asked Jan 13, 2019 in Algorithms by debanjan sarkar Active (3.8k points) | 47 views

+2 votes

0 answers

30

Asymptotic notation
Let f(n) =O(n), g(n)=Ώ(n) and h(n)=Θ(n). Then g(n)+f(n).h(n) is _____? a- Ω($n^{2}$) b- Θ($n^{2}$) c-Ω(n) d-Θ(n)

asked Jan 12, 2019 in Algorithms by bts1jimin (205 points) | 100 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged asymptotic-notations

Recent Posts

Recent Blog Comments