Recent questions tagged time-complexity

0 votes

0 answers

1

homework
I need to find the tight bound of the Fibonacci sequence in dynamic programming (using theta). I only know the bound using big O is O(n). Any idea how to do it?

asked Oct 10 in Algorithms by Mariela Prasetyo (13 points) | 18 views

+1 vote

0 answers

2

radix sort counting sort
Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these number in linear time? 1)Counting Sort 2)Radix Sort 3)Bubble Sort 4)Merge Sort.

asked Oct 9 in Algorithms by Kaushal Sanadhya (61 points) | 33 views

0 votes

0 answers

3

Merge Sort Doubt
what is the recurrence relation for merge sort?

asked Oct 6 in Algorithms by aditi19 Junior (849 points) | 24 views

+1 vote

3 answers

4

recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.

asked Oct 4 in Algorithms by sushmita Boss (14.6k points) | 63 views

0 votes

0 answers

5

Prove that for any constant c > 0, (log n)^c = o(n).

asked Oct 3 in Algorithms by Ojamajo Conan (35 points) | 9 views

0 votes

1 answer

6

time complexity
If both of the algorithms A and B need O(nlogn) time then they both are equally efficient and finish in same amount of time. TRUE OR FALSE

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 60 views

0 votes

1 answer

7

MIT assignment
Find the complexity of the following code fragment: int i = 1; for(; i <= n logn; i + +) { for(i + +; i <= n; i + +) { print(1) } }

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 76 views

0 votes

2 answers

8

Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?

asked Sep 28 in Algorithms by mohitrai0_0 (157 points) | 49 views

+1 vote

1 answer

9

MIT ASSIGNMENT
Find the complexity of the following function when called with some integer n: void foo(n) { int i,j,k,x=0; for (i=1 ; i ≤ n ; i++) for (j=1 ; j ≤ i * i ; j++) { for ( k = 1 ; k ≤ j ; k++) { x=x+10; } }

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 75 views

0 votes

1 answer

10

MIT ASSIGNMENT
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 48 views

0 votes

1 answer

11

MIT assigment
Arrange the following functions in their increasing order of complexities. $f(n) = n ^{0.999999} * logn$ ($log n$ is not in power) $g(n) = 10000 n$ $h(n) = n^{2}$ $k(n) = (1.000001)^{n}$ $p(n) = \frac{2 ^{√n}}{ n^{2}}$ $q(n) = \frac{n^{1.000001}}{logn}$

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 118 views

0 votes

0 answers

12

mit assignment
State true/false f(n) != O(g(n)) and g(n) != O(f(n))

asked Sep 28 in Algorithms by sushmita Boss (14.6k points) | 31 views

0 votes

0 answers

13

Cormen
Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a sub-graph of $T$ induced by $V'$ and let $G’$ be a sub-graph of $G$ induced by $V'$. Prove that If $T'$ is connected , then $T'$ is a minimum weight spanning tree of graph $G′$

asked Sep 27 in Algorithms by sushmita Boss (14.6k points) | 34 views

0 votes

2 answers

14

Self doubt
Find the Complexity of: T(N) = T(${\sqrt{N}}$) + NlogN

asked Sep 24 in Algorithms by Sirjanpreet Singh Ba (7 points) | 43 views

0 votes

0 answers

15

Solving recurrence relation by substitution method

asked Sep 24 in Compiler Design by GateAspirant999 Active (2.7k points) | 11 views

0 votes

0 answers

16

Cormen Appendix A
Why does (1/3+1/c) <=1?

asked Sep 22 in Algorithms by Noddy (27 points) | 12 views

0 votes

1 answer

17

Asymptotic-notations
f(n)=2(log2 n)2 , g(n)=log2n+1 How to give relation between them?.

asked Sep 22 in Algorithms by Vishnathan (189 points) | 32 views

0 votes

0 answers

18

Quick Sort Analysis
Consider the Quicksort algorithm.Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements.Let T(n) be the number of comparisons required to sort n elements.Then: A. T(n)<=2T(n/5)+n B. T(n)<=T(n/5)+T(4n/5)+n C. T(n)<=2T(4n/5)+n D. T(n)<=2T(n/2)+n

asked Sep 21 in Algorithms by Vaishnavi01 (153 points) | 54 views

0 votes

1 answer

19

time-complexcity
for(i=0;i<n;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) what is the time complexity of above psudo code? explain.

asked Sep 21 in Algorithms by balaganesh (125 points) | 39 views

0 votes

0 answers

20

Algorithms Complexity

asked Sep 21 in Algorithms by Vaishnavi01 (153 points) | 80 views

0 votes

1 answer

21

conceptual doubt
WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??

asked Sep 20 in DS by sushmita Boss (14.6k points) | 82 views

0 votes

1 answer

22

Time complexity of code given

asked Sep 17 in Algorithms by GateAspirant999 Active (2.7k points) | 48 views

0 votes

0 answers

23

Time complexity of given code using "finite" geometric series

asked Sep 15 in Mathematical Logic by GateAspirant999 Active (2.7k points) | 9 views

0 votes

1 answer

24

Verification of the Time Complexities
Can someone please validate the following respective time complexities?

asked Sep 13 in Algorithms by chauhansunil20th Junior (505 points) | 25 views

0 votes

1 answer

25

TESTBOOK TEST SERIES

asked Sep 12 in Algorithms by Avik Chowdhury Junior (827 points) | 64 views

0 votes

1 answer

26

class book
C function let n>=m. int gcd(n,m) { if(n%m==0) return m; n=n%m; return gcd(m,n); } time complexity

asked Sep 11 in Algorithms by amit166 (211 points) | 24 views

0 votes

2 answers

27

class notes
find time complexity f(int n){ int i=1; while(i<n) { int j=n; while(j>0) j=j/2; i=i*2; } }

asked Sep 11 in Algorithms by amit166 (211 points) | 23 views

0 votes

1 answer

28

gatebook
Q2. int A(int) { if(n<=2) return 1; else return (A(√n)+n); } time complexity

asked Sep 11 in Algorithms by amit166 (211 points) | 18 views

0 votes

1 answer

29

gatebook
Q.1 int A(int n){ if(n==2) return 1; else{ for(int j=1;j<=n;j++) printf(" * "); return(A(√n)); } } Time complexity

asked Sep 11 in Algorithms by amit166 (211 points) | 16 views

0 votes

0 answers

30

Time Complexity
Please help with the following in Time Complexity. 1)Show that the following order-of-magnitude results hold: a)3n=O(n!) b)(n3 -2n)/(n+1)=theta(n2) c)n3 /log(n+1)=O(n3) but not O(n2) 2)What is wrong with the following argument? x=O(n4),y=O(n2),therefore x/y=O(n2). 3) What is ... the following argument? f(n)=O(n2)+O(n), so that f(n)-g(n)=O(n2 )+O(n)-O(n2). Therefore, f(n)-g(n)=O(n)

asked Sep 10 in Algorithms by Devshree Dubey Boss (13.6k points) | 39 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 time-complexity

Recent Posts

Recent Blog Comments