menu
search
Log In
Quick search syntax
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

Subjects

Recent questions tagged asymptotic-notations

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged asymptotic-notations

0 votes
0 answers
1
Introduction to Algorithm - Cormen
I didn't understand Big-O notation: This is CORMEN exercise problem - 3.1-2 Solution link: https://www.csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf
I didn't understand Big-O notation: This is CORMEN exercise problem - 3.1-2 Solution link: https://www.csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf
asked Jul 23, 2018 in Algorithms Swapnil Naik 157 views
0 votes
1 answer
2
Masters theorem
Solve by using master's theorem
Solve by using master's theorem
asked Jul 17, 2018 in Algorithms bts 194 views
1 vote
1 answer
3
design and analysis of algorithms.
which of the following estimates are true? Explain with valid reasons. a) (2n)! is theta (n)! b) log((2n)!) is theta (log(n)!)
which of the following estimates are true? Explain with valid reasons. a) (2n)! is theta (n)! b) log((2n)!) is theta (log(n)!)
asked Jul 14, 2018 in Algorithms AIkiran01 835 views
1 vote
0 answers
4
Algorithms-Time Complexity
What is the time complexity of the below code? for($k=n^{10};k \geq 5;k=k^{\frac{1}{7}},k=k^2$) { $k=k^5;$ $k=k-10$ } My answer comes to be $O(log_{\frac{7}{10}}log_5(n^{10}))$ Please verify.
What is the time complexity of the below code? for($k=n^{10};k \geq 5;k=k^{\frac{1}{7}},k=k^2$) { $k=k^5;$ $k=k-10$ } My answer comes to be $O(log_{\frac{7}{10}}log_5(n^{10}))$ Please verify.
asked Jul 14, 2018 in Algorithms Ayush Upadhyaya 252 views
4 votes
0 answers
5
time complexity
for(int i=0; i < n; i++) { for(int j=0; j < (2*i); j+=(i/2)) { cout<<"Hello Geeks"; } } is it o(nlogn)??
for(int i=0; i < n; i++) { for(int j=0; j < (2*i); j+=(i/2)) { cout<<"Hello Geeks"; } } is it o(nlogn)??
asked Jul 10, 2018 in Algorithms vijju532 672 views
2 votes
2 answers
6
what is the time complexity for the below question ?
For the below code : foo() { for(i=1;i<=n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) c++; } } } Here k is executing j-1 times and j is executing i times and i is executing n^2 times , so first ... getting order of n^8 .But this is getting too large , I checked with an example , it is not matching ,So please correct where I went wrong .
For the below code : foo() { for(i=1;i<=n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) c++; } } } Here k is executing j-1 times and j is executing i times and i is executing n^2 times , so first I am doing summation from k=0 to k=j-1 over k ... 1 to n^2 , I am getting order of n^8 .But this is getting too large , I checked with an example , it is not matching ,So please correct where I went wrong .
asked Jun 28, 2018 in Algorithms radha gogia 362 views
1 vote
1 answer
7
Self doubt
Consider the following functions
Consider the following functions
asked Jun 28, 2018 in Algorithms Doley 70 views
0 votes
1 answer
8
what is the tightest bound for the below functions ?
n2 + O(n2) = Theta(n2) I am not getting how can we say that tightest bound is in terms of theta , because theta(n2 ) implicitly implies Big-Omega(n2 ) and Big O(n2 ) , Now If we say the function f(n) is Big-Omega(n2 ... will never get a function greater than n2 so how can we say the tightest bound to be Big-Omega(n2 ) ? Please explain briefly .
n2 + O(n2) = Theta(n2) I am not getting how can we say that tightest bound is in terms of theta , because theta(n2 ) implicitly implies Big-Omega(n2 ) and Big O(n2 ) , Now If we say the function f(n) is Big-Omega(n2 ) , then f(n) can be any of the ... but on LHS , we will never get a function greater than n2 so how can we say the tightest bound to be Big-Omega(n2 ) ? Please explain briefly .
asked Jun 24, 2018 in Algorithms radha gogia 226 views
0 votes
0 answers
9
Asymptotic Complexity
$T\left ( n,c \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( c,n \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( n,n \right )=\Theta \left ( n \right )+T\left ( n,\frac{n}{2} \right )$ How to find complexity for this recurrence relation?
$T\left ( n,c \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( c,n \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( n,n \right )=\Theta \left ( n \right )+T\left ( n,\frac{n}{2} \right )$ How to find complexity for this recurrence relation?
asked Jun 22, 2018 in Algorithms srestha 148 views
1 vote
0 answers
10
Time Complexity
What will be the time complexity of the following algorithm ? A(n){ if(n<=1) return 1; for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } } }
What will be the time complexity of the following algorithm ? A(n){ if(n<=1) return 1; for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } } }
asked Jun 17, 2018 in Algorithms kartikeya2812 182 views
2 votes
1 answer
11
Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this ... masters theorem, like the way Tauhin Gangwar has solved here - https://gateoverflow.in/60532/find-tc-t-n-2t-n-1-2-1
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this equation could be solved using masters theorem, like the way Tauhin Gangwar has solved here - https://gateoverflow.in/60532/find-tc-t-n-2t-n-1-2-1
asked Jun 11, 2018 in Algorithms Hardik Maheshwari 1.4k views
0 votes
0 answers
12
Cormen 3rd edition Problem 3-2 part (f)
Indicate for pair of expressions (A,B) whether A is O, o, Ω, ω or of B? A = lg(n!) B = lg(n^n)
Indicate for pair of expressions (A,B) whether A is O, o, Ω, ω or of B? A = lg(n!) B = lg(n^n)
asked Jun 11, 2018 in Algorithms Aarvi Chawla 63 views
1 vote
2 answers
13
Cormen
T(n)=T(n-1)+2n where T(1)=1 Solve recurrence relation
T(n)=T(n-1)+2n where T(1)=1 Solve recurrence relation
asked Jun 8, 2018 in Algorithms vijju532 397 views
0 votes
0 answers
14
Complexity
#DAA Prove that if: f(n) = amnm + am-1nm-1 + am-2nm-2 + am-3nm-3 + .........+ a1n + a0 then f(n) = O(nm) .
#DAA Prove that if: f(n) = amnm + am-1nm-1 + am-2nm-2 + am-3nm-3 + .........+ a1n + a0 then f(n) = O(nm) .
asked Jun 6, 2018 in Algorithms Naveen Kumar 3 65 views
1 vote
2 answers
15
Analysis of algorit
Which of the following statements is/are valid? 1. Time Complexity of QuickSort is Θ(n^2) 2. Time Complexity of QuickSort is O(n^2) 3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). 4. Time complexity of all computer algorithms can be written as Ω(1)
Which of the following statements is/are valid? 1. Time Complexity of QuickSort is Θ(n^2) 2. Time Complexity of QuickSort is O(n^2) 3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). 4. Time complexity of all computer algorithms can be written as Ω(1)
asked Jun 6, 2018 in Algorithms jatinkumar 970 views
0 votes
1 answer
16
Big O
asked May 10, 2018 in Algorithms Sanjay Sharma 207 views
0 votes
1 answer
17
Cormen 3rd edition Exercise 4.4.9
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) =T(an)+T((1-a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant.
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) =T(an)+T((1-a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant.
asked Apr 27, 2018 in Algorithms Neha_16 450 views
0 votes
1 answer
18
Asymtotic notation
Big Omega question : 5n+3>=C2n for which value of c and n condition satisfies?
Big Omega question : 5n+3>=C2n for which value of c and n condition satisfies?
asked Apr 17, 2018 in Algorithms once_2019 73 views
0 votes
1 answer
19
Zeal Indore
Compute: T(n) = 2^nT(n/2) +n^n 1)theta(n^n) 2)theta(nlogn) 3)theta(n^nlogn) 4)none of these.
Compute: T(n) = 2^nT(n/2) +n^n 1)theta(n^n) 2)theta(nlogn) 3)theta(n^nlogn) 4)none of these.
asked Apr 15, 2018 in Algorithms Harshit Pandey 202 views
2 votes
2 answers
21
Algorithms time Complexity
What is the time complexity of this code?
What is the time complexity of this code?
asked Apr 5, 2018 in Algorithms gauravkc 367 views
0 votes
0 answers
22
Recurrence
When T(n) = a T(n/b) + f(n) If on solving we get g(n) as upper bound solution for the recurrence. Is f(n) = O( g(n) ) always correct?
When T(n) = a T(n/b) + f(n) If on solving we get g(n) as upper bound solution for the recurrence. Is f(n) = O( g(n) ) always correct?
asked Apr 3, 2018 in Algorithms smsubham 140 views
1 vote
1 answer
23
Cormen 4.3.8
Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.
Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.
asked Apr 2, 2018 in Algorithms Mk Utkarsh 240 views
2 votes
1 answer
24
Cormen 4.4-5
Use the recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n-1)+T($\frac{n}{2}$)+n. Use substitution method to verify the answer.
Use the recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n-1)+T($\frac{n}{2}$)+n. Use substitution method to verify the answer.
asked Mar 9, 2018 in Algorithms Tesla! 480 views
1 vote
1 answer
25
Introduction to Algorithm 3-6
For a given constant c $\in \mathbb{R}$, we define the iterated function $f_{c}^{*}$ by $f_{c}^{*}$(n)=min{${i\geq 0: f^{(i)}(n)<c}$} For each of the following function f(n) and constants c, give as tight a bound as possible on $f_{c}^{*}$ f(n) c $f_{c}^{*}$(n) $\sqrt{n}$ 2 $\sqrt{n}$ 1 n/lg n 2
For a given constant c $\in \mathbb{R}$, we define the iterated function $f_{c}^{*}$ by $f_{c}^{*}$(n)=min{${i\geq 0: f^{(i)}(n)<c}$} For each of the following function f(n) and constants c, give as tight a bound as possible on $f_{c}^{*}$ f(n) c $f_{c}^{*}$(n) $\sqrt{n}$ 2 $\sqrt{n}$ 1 n/lg n 2
asked Mar 7, 2018 in Algorithms Tesla! 165 views
1 vote
2 answers
26
Doubt in Asymptotic Analysis
Find theta bound for f(n)=$n^2/2 -n/2$
Find theta bound for f(n)=$n^2/2 -n/2$
asked Mar 6, 2018 in Algorithms Devshree Dubey 171 views
2 votes
1 answer
27
Equivalent Complexity
Given f(n) = ω(n2). Which of the following can never hold? a. f(n) = O (n3) b. f(n) = Ω (n2) c. f(n) = θ (n2) d. f(n) = ω (n)
Given f(n) = ω(n2). Which of the following can never hold? a. f(n) = O (n3) b. f(n) = Ω (n2) c. f(n) = θ (n2) d. f(n) = ω (n)
asked Jan 30, 2018 in Algorithms Tuhin Dutta 208 views
2 votes
1 answer
28
Algorithms:Asymptotic Notations
plz help me . how to solve that type of question
plz help me . how to solve that type of question
asked Jan 27, 2018 in Algorithms 92komal 162 views
3 votes
1 answer
29
time complexity
time complexity questions like : h(n)=O(n2); f(n)= O(logn); g(n)=omega(n2); what is the complexity of :::: 1. h(n)-g(n)=?? 2. h(n)-f(n)=??? elaborate plz
time complexity questions like : h(n)=O(n2); f(n)= O(logn); g(n)=omega(n2); what is the complexity of :::: 1. h(n)-g(n)=?? 2. h(n)-f(n)=??? elaborate plz
asked Jan 22, 2018 in Algorithms akankshadewangan24 198 views
2 votes
0 answers
30
MadeEasy Test Series 2018: Algorithms - Asymptotic Notations
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
asked Jan 22, 2018 in Algorithms ashish pal 246 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...