algoPhobic
New member
- Joined
- Jan 17, 2017
- Messages
- 15
Hello,
I'm a computer science enthusiast. I'm trying to teach myself Algorithm Analysis. I'm not in a formal classroom type situation. So, I do not have the luxury of getting clarification or guidance from a teacher. All I have to go on is my computer science books, and faded memories of my grade school and high school algebra.
In Skiena's, The Algorithm Design Manual, there is a "key observation" {2n+1 = 2· 2n} in the following problem statement that I'm failing to understand...
I understand the majority of what is being explained there. It's only the 2n+1 = 2· 2n that has me stumped. Please, can anybody talk me through an explanation of why 2n+1 = 2· 2n
I would be grateful if anybody could please advise me on what particular Algebra concepts I should bone up on that would give me a quick high level understanding of 2n+1 = 2· 2n.
Thank you in advance for your help.
I'm a computer science enthusiast. I'm trying to teach myself Algorithm Analysis. I'm not in a formal classroom type situation. So, I do not have the luxury of getting clarification or guidance from a teacher. All I have to go on is my computer science books, and faded memories of my grade school and high school algebra.
In Skiena's, The Algorithm Design Manual, there is a "key observation" {2n+1 = 2· 2n} in the following problem statement that I'm failing to understand...
Code:
[I]Is 2[SUP]n+1[/SUP] = O(2[SUP]n[/SUP])? Well, f(n) = O(g(n)) iff (if and only if) there exists a
constant c such that for all sufficiently large n f(n) ≤ c · g(n). Is there? The
key observation is that [B]2[SUP]n+1[/SUP] = 2· 2[SUP]n[/SUP][/B], so 2 · 2n ≤ c · 2[SUP]n[/SUP] for any c ≥ 2.[/I]
I understand the majority of what is being explained there. It's only the 2n+1 = 2· 2n that has me stumped. Please, can anybody talk me through an explanation of why 2n+1 = 2· 2n
I would be grateful if anybody could please advise me on what particular Algebra concepts I should bone up on that would give me a quick high level understanding of 2n+1 = 2· 2n.
Thank you in advance for your help.