Recent questions tagged time-complexity

0 votes

0 answers

1

Time Complexity
What will be TC here? Ans given $O(n^{2})$ , while I am getting $O(n)$

asked 5 hours ago in Algorithms by srestha Veteran (91.8k points) | 3 views

0 votes

0 answers

2

Heap data structure
a)Deletion of smallest element in heap b)Insertion of an element in a heap will take $O(n)$ or $O(logn)$ time?

asked 1 day ago in DS by srestha Veteran (91.8k points) | 26 views

0 votes

0 answers

3

Algorithm(Goodrich)1.7
Show that $log^{3}n$ is $o\left ( n^{1/3} \right )$

asked 3 days ago in Algorithms by srestha Veteran (91.8k points) | 56 views

0 votes

1 answer

4

made easy, recurrence relations
which of the following cannot be solved using masters theorem? a) T(n) = 2T(n/2) + n/logn b) T(n) = 2T(n/2) + logn c)T(n)=T(n/2)+logn d) non of these

asked 6 days ago in Algorithms by manvi_agarwal (37 points) | 93 views

0 votes

1 answer

5

Self Doubt

asked Aug 11 in Algorithms by eswaraleti143 (17 points) | 35 views

0 votes

2 answers

6

masters theorem
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2

asked Aug 10 in Algorithms by manvi_agarwal (37 points) | 30 views

0 votes

3 answers

7

Time Complexity
What is the time complexity of the following? for(i=0; i < n *n ; i = i *i) print("*");

asked Aug 9 in Algorithms by smsubham Loyal (6.8k points) | 50 views

0 votes

0 answers

8

Made Easy Algorithms
How to calculate the time complexity for finding repeated elements in an array of n elements using linear search and binary search?

asked Aug 6 in Algorithms by Sambhrant Maurya Junior (609 points) | 22 views

0 votes

0 answers

9

Made Easy algorithms
Given an array of n elements, two elements in the array a[i] and a[j] are said to be inverse only if a[i]>a[j] && i<j. What is the time complexity required to find the number of inverses in the given array using merge sort? a) O(n) b) O(n2) c) O(nlogn) d) O(logn)

asked Aug 6 in Algorithms by Sambhrant Maurya Junior (609 points) | 18 views

0 votes

0 answers

10

Masters Theorem
How can we apply Masters theorem to these equations : T(n) = 16*T(n/4) + n! and T(n) = 4*T(n/2) + cn Please explain the process.

asked Aug 6 in Algorithms by Rahul Ranjan 1 (141 points) | 30 views

0 votes

0 answers

11

Time complexity
What is the time complexity of the following code snippet? function(n) { for i=1 to n { if(n<=10000) { for j=1 to n { for k=1 to n { val = val + 1; } } } else { for j=1 to n val = val + 1 } } } I am getting answer as O(n$^{2}$). But answer is given as O(1). Explain briefly.

asked Aug 5 in Algorithms by Siddharth Bhardawaj Junior (919 points) | 26 views

0 votes

0 answers

12

Time complexity
What is the time complexity of the following code? int j = 0; for(i=0;i<n;i++) { for(i=0;i<2n;i++) { while(j<n) { j++; } } } a) O(n$^{4}$) b) O(n$^{3}$) c) O(n$^{2}$) d) O(n) I am getting option O(n$^{2}$) and answer is given O(n) Explain briefly.

asked Aug 5 in Algorithms by Siddharth Bhardawaj Junior (919 points) | 59 views

+1 vote

2 answers

13

Sorting
Could a binary search tree be built using o(n lg n) comparisons in the comparison model? Explain why or why not.

asked Aug 2 in Algorithms by Ravi Dubey (121 points) | 27 views

0 votes

2 answers

14

time complexity
main() { int i,count; for (i=1; i<=n; i++) { for(i=1; i<=(n*n); i++) { for(i=1; i<=(n*n*n); i++) { count++; } } } } What will be the time complexity of the given program?

asked Jul 31 in Algorithms by Bhunesh_Singh (19 points) | 34 views

+1 vote

1 answer

15

MIT_algorithms
I don't understand How?

asked Jul 30 in Algorithms by Rishav Kumar Singh Active (1.9k points) | 56 views

+2 votes

3 answers

16

sorting
When the recurrence relation for both are same , why they both getting different result? Q1. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort? ANSWER: recurrence ... is If for first case it is N(log3/2N) then for second case also it should be N(log4/3N) BUT its not. WHY?

asked Jul 30 in Algorithms by Rishav Kumar Singh Active (1.9k points) | 53 views

+1 vote

0 answers

17

Algorithms
Solve the recurrence relation $T(n) = T(\sqrt{n}) + n$

asked Jul 27 in Algorithms by gauravkc Loyal (6.1k points) | 156 views

0 votes

1 answer

18

Time complexity
Which one is larger $O(√n)$ or $O(log n)$ ?

asked Jul 27 in Algorithms by Vishnathan (89 points) | 44 views

0 votes

1 answer

19

Recurrence Relation
Solve the following recurrence relation :- N(h)=N(h−1)+N(h−2)+1

asked Jul 27 in Programming by bts (137 points) | 63 views

0 votes

0 answers

20

Self Doubt
 void fun(int n, int arr[]) { int i = 0, j = 0; for(; i < n; ++i) while(j < n && arr[i] < arr[j]) j++; } In this question the inner loop runs n times at most because j is not ... wont the outer loop also run n times (incrementing and checking conditions in while) and making the total time complexity to be O(n2)??

asked Jul 24 in Algorithms by harishrajora (51 points) | 27 views

+1 vote

3 answers

21

Online doubt
while solving this recursive equation: T(n)=T(n/3)+T(2n/3)+n; i tried the master theorem ignoring the less long term T(n/3) this gave me : T(n)=T(2n/3)+n; and it leads to O(n) Time complexity. And doing with recursive tree method it gave me N(logN base 3/2).. So what is wrong with master theorem approach?

asked Jul 22 in Algorithms by aaaaaaaa (19 points) | 60 views

0 votes

0 answers

22

Doubt
Can we solve it by master Theorem T(n)=T(n/3)+T(n/4)+6n

asked Jul 19 in Algorithms by bhavnakumrawat5 (139 points) | 101 views

0 votes

1 answer

23

Masters theorem
Solve by using master's theorem

asked Jul 17 in Algorithms by bts (137 points) | 79 views

0 votes

3 answers

24

Masters theorem
Solve using Master's Theorem $T(n)=T(n/2)+$ 2n

asked Jul 16 in Algorithms by Vishnathan (89 points) | 59 views

0 votes

2 answers

25

time complexity
Given f(n) = θ(n), g(n) = Ω(n), h(n) = O(n). Then f(n) + [g(n) ⋅ h(n)] = ? how to solve??

asked Jul 15 in Puzzles by vijju532 (369 points) | 80 views

0 votes

0 answers

26

Time Complexity
Consider the following C code: int f(int x){ if(x<1) return 1; else return f(x-1)+g(x); } int g(int x){ if(x<2) return 1; else return f(x-1)+g(x/2); } Of the following, which best describes the growth of f(x) as a function of x? a) logarithmic b) quadratic c) linear d) exponential please explain.

asked Jul 14 in Algorithms by nishant279 (439 points) | 67 views

+1 vote

0 answers

27

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.

asked Jul 14 in Algorithms by Ayush Upadhyaya Boss (11k points) | 147 views

+1 vote

1 answer

28

TIme complexity
Q.14 What is the time complexity of the following recursive function? int Dosomething (int n) { if(n≤2) return 1; else return (Dosomething (floor(sqrt(n))) + n); (a) Ѳ(n 2 ) (c) Ѳ(log 2 n) (b) Ѳ(nlog 2 n) (d) Ѳ(log 2 log 2 n)

asked Jul 14 in Algorithms by pradeepchaudhary (179 points) | 52 views

+2 votes

2 answers

29

Time Complexity Of the Algorithm
Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by— T(n)= T(n-1) + 1/n, if n>1 = 1, otherwise. The order of the algorithm is— (a) log n (c) n^2 (b) n (d) n*n

asked Jul 14 in Algorithms by pradeepchaudhary (179 points) | 63 views

0 votes

0 answers

30

How to evaluate time complexity for below question ?

asked Jul 11 in Algorithms by radha gogia Loyal (7.2k points) | 117 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