Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 144324

The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.

0 votes

Determine the time complexity of repeated logarithm until not greater than 1

I got it: this algorithm has a nearly-constant complexity, specifically the complexity is $\Theta(\log^{*}(n))$ where $\log^{*}(n) \le 5 \ \forall n \le 2^{16}$
Loris Simonetti's user avatar
1 vote
2 answers
80 views

Determine the time complexity of repeated logarithm until not greater than 1

t <- n while t>1 do t <- log_2(t) I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\text{(3)}(t) = \log_2^{(3)}(t) \\ f^\ …
Loris Simonetti's user avatar
1 vote
1 answer
92 views

Design an optimal algorithm that finds 2 array indices in a sorted array such that $A [i] + ...

Text: Given a non-descending ordered array A and an integer k, design an algorithm to find, if any, the indices of a pair of elements whose sum is equal to k. Discuss the complexity and the optimality …
Loris Simonetti's user avatar
2 votes
1 answer
269 views

Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \en …
Loris Simonetti's user avatar