Recent questions tagged time-complexity

0 votes

0 answers

1

Question_bank
f(n)=O(g(n)) Which of the following is True? 2^f(n)=O(2^(g(n)) log(f(n))=O(log(g(n)) f(n)=O(f(n/2)) f(n)=O(f(n)^2)

asked 5 days ago in Algorithms by Shivam Kasat Junior (811 points) | 26 views

0 votes

0 answers

2

GATEBOOK
Please mention proper approach to solve similar questions

asked Dec 7 in Algorithms by pps121 Active (1.4k points) | 48 views

0 votes

0 answers

3

Time Complexity
What is the time Complexity of this program ? (Do give detailed Answer)

asked Dec 4 in Algorithms by Ashish Roy 1 (111 points) | 88 views

0 votes

1 answer

4

Kth Largest element in Min-Heap
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?

asked Dec 1 in Algorithms by gmrishikumar (461 points) | 57 views

0 votes

1 answer

5

Ace TestSeries
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?

asked Nov 29 in Algorithms by Nidhi Budhraja (203 points) | 53 views

0 votes

0 answers

6

#SELF DOUBT
Prove dijkstra’s algorithm using Heap is O((n+|E|)logn) where n is no.of vertices and |E| is number of edges? Book : Fundamentals of Computer Algorithms By sahni page : 263

asked Nov 28 in Algorithms by OneZero (255 points) | 10 views

0 votes

0 answers

7

#time complexity
T(n)=4T(n/2)+n$^{2}\sqrt{2}$ T.C

asked Nov 24 in Algorithms by amit166 Junior (529 points) | 41 views

+1 vote

1 answer

8

How is the time Complexity of this problem O(n log log n)?

asked Nov 22 in Algorithms by gmrishikumar (461 points) | 148 views

0 votes

1 answer

9

T(n) = sqrt(n) * T(sqrt(n)) + n
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?

asked Nov 22 in Algorithms by gmrishikumar (461 points) | 101 views

0 votes

1 answer

10

Programming (Time Complexity)
What will be time complexity: main() { int sum=0; for(int bound=1;bound<=n;bound*=2) { for(int i=0;i<bound;i++) { for(j=0;j<n;j+=2) { sum+=j; } for(int j=1;j<n;j*=2) { sum*=j; } } } } I think every for loop is participating to find T.C. something*2 means why will it run upto $log n$ and not upto $\frac{n}{2}$

asked Nov 21 in Programming by srestha Veteran (103k points) | 94 views

0 votes

0 answers

11

Karumanchi
There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node? my approach is... As there is no previous pointer so we traverse the list from the starting to just ... complexity as O(n) and space complexity O(1). but in the book the time complexity is mentioned O(1) where am I going wrong?

asked Nov 20 in DS by aditi19 Active (2.1k points) | 35 views

0 votes

0 answers

12

recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused

asked Nov 18 in Algorithms by LavTheRawkstar Active (5.2k points) | 57 views

0 votes

0 answers

13

Time Complexity
How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7

asked Nov 17 in Algorithms by garvit_vijai (149 points) | 47 views

0 votes

0 answers

14

Self Doubt - Quick Sort
Consider the following inputs: 1) 2 2 2 2 2 2 2 2) 1 2 3 4 5 6 7 3) 7 6 5 4 3 2 1 In all three cases, the worst-case time complexity of quicksort is O(n2) My doubt is if I am taking the middle element as a pivot, ... ), right? Can someone explain how we are saying worst-case time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?

asked Nov 16 in Algorithms by garvit_vijai (149 points) | 27 views

0 votes

1 answer

15

What is the value of T(n) for the given recurrence relation

asked Nov 14 in Algorithms by sripo Junior (933 points) | 69 views

0 votes

0 answers

16

Karumanchi
f(n)=$2^n$ g(n)=n! h(n)=$n^{logn}$ which one is true? A) f(n)=O(g(n)) and g(n)=O(h(n)) B) f(n)=$\Omega(g(n)))$ and g(n)=O(h(n)) C) g(n)=O(f(n)) and h(n)=O(f(n)) D) h(n)=O(f(n)) and g(n)=$\Omega(f(n))$

asked Nov 6 in Algorithms by aditi19 Active (2.1k points) | 50 views

0 votes

0 answers

17

Time Complexity for an infinite loop
What is the time complexity for infinite loops Question 1 what is T(n) for this case While(1) { a=a+b; } Question 2 for this case if(1) { for i to n a=a+b } else { for i to n for j to n a=a+b } Edit 2: Compiled the code ... ); return 0; } output I get is 8 6 which means the else case is never executed hence in worst case do we have to consider the else part.

asked Nov 6 in Algorithms by sripo Junior (933 points) | 48 views

0 votes

2 answers

18

Karumanchi

asked Nov 4 in Algorithms by aditi19 Active (2.1k points) | 87 views

0 votes

0 answers

19

Find the Time Complexity
Suppose, we have an array of n elements. find the time complexity to search two elements x, y such that:- a) x+y < 100 b) x+y > 1000 Also, state the algorithm/approach for the same.

asked Nov 4 in Algorithms by Naveen Kumar 3 Active (2.8k points) | 73 views

0 votes

1 answer

20

time complexity of recursive program
What is the time complexity of the following code snippet? Assume "statement" takes $O(1)$ time. int x=0; int A(n) { statement; if(n==1)return 1; else { x + = 4A(n/2)+n^{2} return (x); } } $A)\theta(n^{2}logn)$ $B)\theta(logn)$ $C)\theta(n^{2})$ $D)\theta(nlogn)$

asked Nov 3 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 59 views

0 votes

0 answers

21

Time complexity of the program
Consider the following function(n) { val=0; 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; } } The running time of the above function can best be described by $T(n)=$____________ $A)\theta(n^{3}) $ $B)\theta(n^{2})$ $C)\theta(n)$ $D)\theta(1)$

asked Nov 3 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 60 views

0 votes

0 answers

22

A is polynomially reducible to B
Let there be two problems $A$ and $B$ It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomial reduction is carried out in time of $O(n).$The problem $B$ can be solved in $O(n^{3})$ time. what is the time taken to solve problem $'A'?$ $A)O(n)$ $A)O(n^{3})$ $A)O(2^{n})$ $D)$None of these

asked Nov 3 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 34 views

0 votes

0 answers

23

Runnig time on algorithm
What is the smallest value of $n$ (where $n$ is a natural number) such that an algorithm whose running time is $100\sqrt{n}$ runs faster than an algorithm whose running time is $2^{\frac{n}{2}}$ on the same machine?

asked Nov 1 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 31 views

0 votes

0 answers

24

Self doubt on Asymptotic Notations
The iterated logarithmic function is defined as: $logn=0;$ $if$ $n\leq1$ $(or)$ $logn=1+log(logn);$ $if$ $n>1$ Which of the following is/are $True?$ $(1)logn=O(log(logn))$ $(2)(logn)!=O(logn)$ $(3) logn)^{n}=O((logn)!)$ $A)(1)$ $and$ $(2)$only$ $B)(1) and (3) only $ $C)(2)$ $and$ $(3)$ $only $ $D)(1),(2)$ $and$ $(3) $

asked Nov 1 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 23 views

0 votes

1 answer

25

Recurrence Relations
Given $T(n)=T(\frac{n}{4})+T(\frac{n}{2})+n^{2},$ then $A)T(n)=\theta(n^{3})$ $B)T(n)=\theta(n^{2}logn)$ $C)T(n)=\theta(n^{2})$ $D)T(n)=\theta(n^{3}logn)$

asked Nov 1 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 46 views

+1 vote

1 answer

26

Asymptotic Notations
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true

asked Nov 1 in Algorithms by Lakshman Patel RJIT Boss (20.2k points) | 44 views

0 votes

1 answer

27

Karumanchi
what is the time complexity of function(int n) { if(n<=1) return; for(int i=1; i<n; i++) { printf("*"); } function(0.8n); } i'm getting O(nlogn base 5/4) using the recurrence relation method but in the book it's given O(n) $T(n)=T(\frac{4n}{5})+O(n)$

asked Oct 31 in Algorithms by aditi19 Active (2.1k points) | 80 views

0 votes

0 answers

28

time complexity
What is the time complexity of fun()? int fun(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = i; j > 0; j--) count = count + 1; return count; }

asked Oct 30 in Algorithms by suneetha (379 points) | 46 views

0 votes

1 answer

29

time complexity
for(i=1;i<=n;++i) { j=1; while(j<=n) j=2*j; for(k=1;k<=n;++k) c=c+1; } then what is the time complexity will be?

asked Oct 30 in Algorithms by suneetha (379 points) | 54 views

0 votes

0 answers

30

time complexity
i=n; while(i>0) { j=1; while(j<=n) { j=2*j; } i=i/2; } then what is the time complexity?

asked Oct 30 in Algorithms by suneetha (379 points) | 34 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