Recent questions tagged asymptotic-notations

+1 vote

1 answer

1

Self doubt
Consider the following functions

asked Jun 28, 2018 in Algorithms by Doley (129 points) | 40 views

0 votes

1 answer

2

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 .

asked Jun 24, 2018 in Algorithms by radha gogia Loyal (6.3k points) | 130 views

0 votes

0 answers

3

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?

asked Jun 22, 2018 in Algorithms by srestha Veteran (117k points) | 107 views

+1 vote

0 answers

4

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) } } }

asked Jun 17, 2018 in Algorithms by kartikeya2812 (21 points) | 117 views

+2 votes

1 answer

5

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

asked Jun 11, 2018 in Algorithms by Hardik Maheshwari (93 points) | 413 views

0 votes

0 answers

6

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)

asked Jun 11, 2018 in Algorithms by Aarvi Chawla (365 points) | 37 views

+1 vote

2 answers

7

Cormen
T(n)=T(n-1)+2n where T(1)=1 Solve recurrence relation

asked Jun 8, 2018 in Algorithms by vijju532 Active (1k points) | 126 views

0 votes

0 answers

8

Complexity
#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 by Naveen Kumar 3 Boss (15.2k points) | 45 views

+1 vote

2 answers

9

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)

asked Jun 6, 2018 in Algorithms by jatinkumar (307 points) | 299 views

0 votes

1 answer

10

Big O

asked May 10, 2018 in Algorithms by Sanjay Sharma Boss (48.8k points) | 103 views

0 votes

1 answer

11

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.

asked Apr 27, 2018 in Algorithms by Neha_16 (285 points) | 115 views

0 votes

1 answer

12

Asymtotic notation
Big Omega question : 5n+3>=C2n for which value of c and n condition satisfies?

asked Apr 17, 2018 in Algorithms by once_2019 Junior (643 points) | 49 views

0 votes

1 answer

13

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.

asked Apr 15, 2018 in Algorithms by Harshit Pandey (25 points) | 148 views

0 votes

1 answer

14

time complexity

asked Apr 11, 2018 in Algorithms by Beyonder (499 points) | 108 views

+2 votes

2 answers

15

Algorithms time Complexity
What is the time complexity of this code?

asked Apr 5, 2018 in Algorithms by gauravkc Loyal (7.8k points) | 195 views

0 votes

0 answers

16

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?

asked Apr 3, 2018 in Algorithms by smsubham Loyal (9.8k points) | 120 views

+1 vote

1 answer

17

Cormen 4.3.8
Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.

asked Apr 2, 2018 in Algorithms by Mk Utkarsh Boss (35.7k points) | 141 views

+2 votes

1 answer

18

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.

asked Mar 9, 2018 in Algorithms by Tesla! Boss (18.3k points) | 238 views

+1 vote

1 answer

19

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

asked Mar 7, 2018 in Algorithms by Tesla! Boss (18.3k points) | 83 views

+1 vote

2 answers

20

Doubt in Asymptotic Analysis
Find theta bound for f(n)=$n^2/2 -n/2$

asked Mar 6, 2018 in Algorithms by Devshree Dubey Boss (13.7k points) | 116 views

+2 votes

1 answer

21

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)

asked Jan 30, 2018 in Algorithms by Tuhin Dutta Loyal (9.8k points) | 83 views

+2 votes

1 answer

22

Algorithms:Asymptotic Notations
plz help me . how to solve that type of question

asked Jan 27, 2018 in Algorithms by 92komal (369 points) | 82 views

+3 votes

1 answer

23

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

asked Jan 22, 2018 in Algorithms by akankshadewangan24 Active (4k points) | 131 views

+2 votes

0 answers

24

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 ?

asked Jan 22, 2018 in Algorithms by ashish pal Junior (823 points) | 148 views

+2 votes

1 answer

25

Asymptotic Notation
Given h(n) < f(n) < g(n). statement 1: h(n)=O(f(n)); g(n)=Ω(f(n)) Statement 1 is True / False?

asked Jan 21, 2018 in Algorithms by hacker16 Active (2.7k points) | 215 views

+3 votes

1 answer

26

time complexity

asked Jan 16, 2018 in Algorithms by pranab ray Junior (779 points) | 138 views

0 votes

3 answers

27

time complexity
i am getting t.c as O(n^5) but given answer as O(n^4) what should be the answer

asked Jan 13, 2018 in Algorithms by pranab ray Junior (779 points) | 102 views

+3 votes

1 answer

28

recurrence eq
how to solve this T(n)=T(n−1)+T(n−2) if T(0)=T(1)=1

asked Jan 12, 2018 in Algorithms by iarnav Loyal (8.3k points) | 130 views

0 votes

0 answers

29

divide and conquer
in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1) How to reach this type of analysis where we get to know that we have to divide n into halves?

asked Jan 12, 2018 in Algorithms by iarnav Loyal (8.3k points) | 136 views

+2 votes

1 answer

30

recurrence using Master theorem
can we solve this T(n) = T(n/2) + 1 using master theorem?

asked Jan 11, 2018 in Algorithms by iarnav Loyal (8.3k points) | 254 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