What Are the Time Complexities of These Functions?

  • MHB
  • Thread starter shamieh
  • Start date
  • Tags
    Time
In summary, I summarized the different functions ( $O$, $\Omega$, and $\Theta$) and their relationships to each other. I also provided justifications for each function using specific values and limits.
  • #1
shamieh
539
0
View attachment 4731
Can someone tell me if I'm even doing this correctly? I haven't dealt with TCs in while.
So I got:

$a) h_1(n) = O(n) \implies n$ , $h_2(n) = \Omega (n\log n) \implies n\log n$

$b) h_1(n) = \Omega(\log n) \implies \log n$, $h_2(n) = O(n^{2/5}) \implies n^{2/5}$

(Justification $h_1(n)$: Let $n = 1000 \implies 12(1000)^{2/3} = 524$ and Let $x = 1000 \implies 7 \log(1000) = 48$ so $n^{2/5} > \log(n)$)

(Justification $h_2(n)$: Let $n = 1000 \implies (5(100000000))^{2/5} = 3017.08..$ so $n^{2/5} > O(1)$ (or 1000) )

$c) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(n \log^4 n) \implies n \log^4 n$

$d) h_1(n) = O(\log(n)) \implies \log(n)$, $h_2(n) = \Omega (\log(n^5)) \implies \log(n^5)$

$e) h_1(n) = O(n) \implies n$, $h_2(n) = O(n) \implies n$

(Justification $h_1(n)$: let $n = 1000 \implies 1000^{1.02} = 1148.15 > \log(1000)^{1.02} = 7.17..$)

(Justification $h_2(n)$: let $n = 1000$ to find $1000(1000)log^3 1000 = 3.296.. < 2(1000) = 2000$)

$f) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(\log n) \implies \log n$

(Justification $h_1(n)$: Well $O(n^2) = n^2$ ?)

(Justification $h_2(n)$: $O(\log n) = \log n$) ?

$h) h_1(n) = O(n) \implies n$, $h_2(n) =$ exponential?
 

Attachments

  • q22.png
    q22.png
    27.2 KB · Views: 66
Last edited:
Physics news on Phys.org
  • #2
shamieh said:
$a) h_1(n) = O(n) \implies n$ , $h_2(n) = \Omega (n\log n) \implies n\log n$

You want to format these the way the problem is asking: $h_1(n)=n$, because $1000n-1000=O(n)$. And $h_2(n)=n \, \log(n)$ because $2n \, \log(n)+6n=O(n \, \log(n))$.

$b) h_1(n) = \Omega(\log n) \implies \log n$, $h_2(n) = O(n^{2/5}) \implies n^{2/5}$

(Justification $h_1(n)$: Let $n = 1000 \implies 12(1000)^{2/3} = 524$ and Let $x = 1000 \implies 7 \log(1000) = 48$ so $n^{2/5} > \log(n)$)

$n^{2/3}$ beats $\log(n)$, so you need to have $h_1(n)=n^{2/3}$.

(Justification $h_2(n)$: Let $n = 1000 \implies (5(100000000))^{2/5} = 3017.08..$ so $n^{2/5} > O(1)$ (or 1000) )

$c) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(n \log^4 n) \implies n \log^4 n$

$d) h_1(n) = O(\log(n)) \implies \log(n)$, $h_2(n) = \Omega (\log(n^5)) \implies \log(n^5)$

Don't forget the logarithm rule here: $\log(n^5)=5 \, \log(n)$.

$e) h_1(n) = O(n) \implies n$, $h_2(n) = O(n) \implies n$

This isn't going to work, I'm afraid. On the first one, you need $h_1(n)=n^{1.02}$. Inside the parentheses, the $n$ beats the $\log(n)$, but without the correct exponent, it will not grow fast enough. For $h_2(n)$, you have to have $n \, \log^3(n)$. Exponentiating the logarithm does not have the nice identity that $\log(n^m)=m \, \log(n)$ does.

(Justification $h_1(n)$: let $n = 1000 \implies 1000^{1.02} = 1148.15 > \log(1000)^{1.02} = 7.17..$)

(Justification $h_2(n)$: let $n = 1000$ to find $1000(1000)log^3 1000 = 3.296.. < 2(1000) = 2000$)

$f) h_1(n) = O(n^2) \implies n^2$, $h_2(n) = \Omega(\log n) \implies \log n$

(Justification $h_1(n)$: Well $O(n^2) = n^2$ ?)

(Justification $h_2(n)$: $O(\log n) = \log n$) ?

For $h_2(n)$, you're going to need
$$5^{\log(n)}=\left(10^{\log(5)}\right)^{\log(n)}=10^{\log(5)\cdot\log(n)}=10^{\log\left(n^{\log(5)}\right)}=n^{\log(5)}.$$
You can see here that I've assumed you're using $\log(x)=\log_{10}(x)$. What follows is more general, in case you're using a different base:
$$a^{\log_b(x)}=\left(b^{\log_b(a)}\right)^{\log_b(x)}=b^{\log_b(a) \cdot \log_b(x)}=b^{\log_b\left(x^{\log_b(a)}\right)}=x^{\log_b(a)}.$$
So, in general, $a^{\log_b(x)}=x^{\log_b(a)}.$ I did not know that before now!

$h) h_1(n) = O(n) \implies n$, $h_2(n) =$ exponential?

I think you're going to need more of something like this:
$$n^{\sqrt{n}}=n^{n^{1/2}}=\left(10^{\log(n)}\right)^{n^{1/2}}=10^{n^{1/2}\log(n)}.$$
That's in the format you need for $h_1$. You can do a similar trick for $h_2$.
 
  • #3
Wow thanks so much.. So now I'm on the second part.. (NOTE: I left out $h$ for the time being)

View attachment 4734

But I'm not sure if I'm doing it right. Here is what I have so far:
a) $f_1 = O(f_2)$
b) Not Equal
c) Not Equal
Justification: $n^2 = 1000^2 =$ 1 million while $(1000)\log^4 (1000) = 2.27..$ so we know that $f(x) \notin O(g(x))$
d) $f_1 = O(f_2)$
Justification: $ \log(n) = \log(1000) = 6.907..$ and $ \log(n^5) = 34.538..$ so we know that $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n)$, $∀$ $ n≥n_0| $ $\therefore f_1 = O(f_2)$
e) $f_1 = O(f_2)$
f) Not Equal
 

Attachments

  • question3.png
    question3.png
    19.3 KB · Views: 58
  • #4
a) $f_1 = O(f_2)$
b) $f_1 = O(f_2)$
c)
According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 5$ for:

$0 \le f_1(n) \le c * f_2(n) \implies (10)^2 + (10)\log(10) \le (5)((10)\log^4 (10) + \sqrt{10})$
= $0 \le 123 \le 1405 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{n^2 + n \log n}{n \log ^4 n + \sqrt{n}} = \infty$

$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

d)
According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 5$ for:

$ 0 \le f_1(n) \le c * f_2(n) \implies 3\log(10) + 3 \le (5)(\log (10^4) + 2)$
= $0 \le 9.9077 \le 56.05 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{3\log(n) + 3}{\log(n^5) + 2} = \frac{3}{5}$

$\therefore f_1 = \Theta(f_2)$

e)
$f_1 = O(f_2)$
$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

f)
$f_1 = O(f_2)$
$\therefore f_1 = \Omega(f_2) \implies f_1 = \Theta(f_2)$

h) According to the definition I know that: $f(x)=O(g(x))$ iff $∃$ positive constants $C$ and $n_0 |0≤f(n)≤c∗g(n), ∀ n≥n_0|$

So letting $n = 10$, $c = 1$ for:

$ 0 \le f_1(n) \le c * f_2(n) \implies 10^{\sqrt{10}} + 3 \le (1)(sqrt{10}^{10})$
= $0 \le 1453 \le 100,000 \implies f_1 = O(f_2)$

Using the fact that:

View attachment 4736

Then we know that $\lim_{n\rightarrow\infty}$ $\frac{n^{\sqrt{n}}}{\sqrt{n}^{n}} = 0$
$\therefore f_1 \in O(f_2)$ but $f_1 \ne \Omega(f_2), f_1 \ne \Theta(f_2)$
 

Attachments

  • thefact.png
    thefact.png
    6.6 KB · Views: 51

FAQ: What Are the Time Complexities of These Functions?

What is time complexity in computer science?

Time complexity in computer science refers to the measure of the amount of time it takes for a program or algorithm to run. It is used to analyze the efficiency and performance of an algorithm based on the input size.

How is time complexity represented?

Time complexity is typically represented using Big O notation, which is a mathematical notation that describes the worst-case scenario for the time taken by an algorithm to run. It helps to classify algorithms based on their growth rate and scalability.

Why is it important to consider time complexity?

Considering time complexity is crucial for optimizing the performance of computer programs. It helps in identifying inefficient algorithms and finding more efficient alternatives. It also allows for predicting the scalability of a program and estimating how long it will take to run on larger inputs.

What are the factors that affect time complexity?

The main factors that affect time complexity are the input size and the structure of the algorithm. The number of times a loop is executed, the number of recursive calls, and the number of operations performed on the input all contribute to the time complexity of an algorithm.

Can time complexity be improved?

Yes, time complexity can be improved by using more efficient algorithms or by optimizing the existing algorithm. This can involve reducing the number of operations, eliminating unnecessary loops, or using data structures that have faster access times. However, it is important to balance time complexity with other factors, such as space complexity and code readability, when making improvements.

Similar threads

Replies
11
Views
4K
Replies
28
Views
5K
5
Replies
156
Views
18K
Replies
2
Views
10K
Replies
38
Views
7K
Replies
125
Views
18K
Back
Top