Dark Mode

Recent activity by Narasimhan

1 answer

1

How to determine the time complexity of this loop?
// func() is any constant root function for (int i = n; i > 0; i = func(i)) { // some O(1) expressions or statements } "In this case, i takes values n, n1/k, (n1/k)1/k = n1/k2, ... do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/

asked in Algorithms Nov 7, 2017

893 views

1 answer

2

Time Complexity
$T(n)=4 T(n/2) + n^2 \sqrt{2}$ I have solved this by back substitution .. and it forms equations of the form $4k T(n/2k) + k n^2 \sqrt 2$ its giving time complexity as n2 + n2 log2n the answer is Theta(n2.5). i have two questions .. a) how can we get Theta(n2.5). b) is n2 log2n Asymptotically faster than n2 ?

commented in Algorithms Nov 6, 2017

1.0k views

2 answers

3

Fibonacci Series Complexity
PLEASE EXPLAIN HOW TO APPROACH THESE KIND OF PROBLEMS

answer edited in Algorithms Nov 6, 2017

547 views

5 answers

4

GATE CSE 2004 | Question: 29
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$

answered in Algorithms Nov 6, 2017

28.2k views